Science and Technology news... :: View topic

plouffe · Guest

Hello,

Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

....but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.

Simon Plouffe

Guest · Posted: Sat Jul 12, 2008 1:08 pm Post subject: Re: Maple fibonacci bug ?

plouffe schrieb:
[quote]
Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

...but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.

[/quote]
I can>t tell why Maple fails, but I have verified that
fibonacci(754966) indeed ;-) exists (Derive 6.10):

fibonacci(n):=([[0,1],[1,1]]^n) SUB 1 SUB 2
fibonacci(754966)
16342705823785353270544771916388648463196561563760910050296708513979272567741~
43724504288069233998207285821600918504532636469781895967378743833777781533554~
68587366328397236472590482995176947342450055119385564253854189348555236456510~
21658143375137866489068225857415714283750680336019311001502874887334170820611~
87447594737014294691609299576300174395148806737892133279695428410553579490199~
[...........................................................................]
55677286747819881221042623317019498707011392469581831144127314327775950115516~
66307631754422426183851325743889837395685253670657527332664531789227161205493~
38948461237369042400983149645380944643650097854168013199063373451377723250481~
32665024743886228215643500207159774940467921701737458241175074481684216816053~
93966598257955927745328385221998619641487903876941722496899865956086017988915~
330863

I can mail you the full number (160 kB) if you want. Your question
would be easier to answer if you could let us know the algorithm
implemented in Maple>s combinat.

Martin.

plouffe · Guest

by using interface(verboseproc=2); you can see the routine :

fibonacci:=proc(n, x)
local i, b, p, f1, f2, s1, s2, s3, r;
option `Copyright (c) 1990 by the University of Waterloo. All rights
reserved.`;
if type([args], '[integer]') then
if n = 0 then return 0 end if;
if n < 0 then return (-1)^(1 - n)*procname(-n) end if;
p := n;
for i from 0 while p <> 0 do p := iquo(p, 2, 'r'); b[i] := r
end do;
f1 := 0;
f2 := 1;
for i from i - 2 by -1 to 0 do
s1 := f2^2;
s2 := 2*f2*f1;
f1 := s1 + f1^2;
f2 := s1 + s2;
if b[i] = 1 then s3 := f2 + f1; f1 := f2; f2 := s3 end if
end do;
f2
elif type([args], '[integer, algebraic]') then
if n < 0 then (-1)^(1 - n)*procname(-n, x)
elif n = 0 then 0
elif n = 1 then 1
else procname(n, x) := normal(x*procname(n - 1, x) +
procname(n - 2, x))
end if
elif type(n, 'numeric') then error "1st argument must be an
integer"
else 'procname(args)'
end if
end:

It seems that (at least on my system) the range 754966 to 755019 is
faulty, I have no idea why.

Simon Plouffe

plouffe · Guest

On 12 juil, 16:56, Axel Vogt <&nore...@axelvogt.de> wrote:
[quote]G. A. Edgar wrote:
In article
58836ac0-9944-4d13-93cb-15b7d8a49...@f36g2000hsa.googlegroups.com>,
plouffe <simon.plou...@gmail.com> wrote:

fibonacci(754966);

I did it in Maple 12 on Mac OS X (Intel Xeon CPU).
The result came in 0.085 seconds

tt := time(): fibonacci(754966); time()-tt;
16342705823785353270544771916388648463196561563760910050296708513979272
56774143724504288069233998207[...157579 digits...]744816842168160539396
65982579559277453283852219986196414879038769417224968998659560860179889
15330863
0.085

From the posts header I guess Plouffe is using NT (in French)
and for Maple12 on Win XP (both classic and standard interface)
I have the same problem, it works however up to version 11.
[/quote]
I use the maple with the terminal interface, not the graphic interface
on win xp sp3.

G. A. Edgar · Guest

In article
<58836ac0-9944-4d13-93cb-15b7d8a49f32@f36g2000hsa.googlegroups.com>,
plouffe <simon.plouffe@gmail.com> wrote:

[quote]fibonacci(754966);
[/quote]
I did it in Maple 12 on Mac OS X (Intel Xeon CPU).
The result came in 0.085 seconds

[quote]tt := time(): fibonacci(754966); time()-tt;
16342705823785353270544771916388648463196561563760910050296708513979272[/quote]
56774143724504288069233998207[...157579 digits...]744816842168160539396
65982579559277453283852219986196414879038769417224968998659560860179889
15330863
0.085

--
G. A. Edgar http://www.math.ohio-state.edu/~edgar/

Axel Vogt · Guest

G. A. Edgar wrote:
[quote]In article
58836ac0-9944-4d13-93cb-15b7d8a49f32@f36g2000hsa.googlegroups.com>,
plouffe <simon.plouffe@gmail.com> wrote:

fibonacci(754966);

I did it in Maple 12 on Mac OS X (Intel Xeon CPU).
The result came in 0.085 seconds

tt := time(): fibonacci(754966); time()-tt;
16342705823785353270544771916388648463196561563760910050296708513979272
56774143724504288069233998207[...157579 digits...]744816842168160539396
65982579559277453283852219986196414879038769417224968998659560860179889
15330863
0.085
[/quote]

From the posts header I guess Plouffe is using NT (in French)
and for Maple12 on Win XP (both classic and standard interface)
I have the same problem, it works however up to version 11.

Axel Vogt · Guest

plouffe wrote:
[quote]On 12 juil, 16:56, Axel Vogt <&nore...@axelvogt.de> wrote:
G. A. Edgar wrote:
In article
58836ac0-9944-4d13-93cb-15b7d8a49...@f36g2000hsa.googlegroups.com>,
plouffe <simon.plou...@gmail.com> wrote:
fibonacci(754966);
I did it in Maple 12 on Mac OS X (Intel Xeon CPU).
The result came in 0.085 seconds
tt := time(): fibonacci(754966); time()-tt;
16342705823785353270544771916388648463196561563760910050296708513979272
56774143724504288069233998207[...157579 digits...]744816842168160539396
65982579559277453283852219986196414879038769417224968998659560860179889
15330863
0.085
From the posts header I guess Plouffe is using NT (in French)
and for Maple12 on Win XP (both classic and standard interface)
I have the same problem, it works however up to version 11.

I use the maple with the terminal interface, not the graphic interface
on win xp sp3.
[/quote]
Ok, so all 3 have this problem.

It is located in the last step of the loop for i=0, but not
through b[0] (what I guessed first), may be an interfacing
problem with GMP which is (possibly) used below Maple here.

Guest · Posted: Sat Jul 12, 2008 9:12 pm Post subject: Re: Maple fibonacci bug ?

Axel Vogt schrieb:
[quote]
It is located in the last step of the loop for i=0, but not
through b[0] (what I guessed first), may be an interfacing
problem with GMP which is (possibly) used below Maple here.
[/quote]
Are you referring to the second loop (the loop with descending i)? In
that case I would suspect some spurious memory allocation problem as
f1, f2, s1, s2, s3 are growing to around 160k digits. Here is a
(slightly simplified) Derive 6.10 equivalent of the Maple procedure:

fibonacci(n,i:=1,b:=[],f1:=0,f2:=1,s1,s2,s3):=PROG(~
IF(NOT(INTEGER?(n)),RETURN("argument must be an integer")),~
IF(n=0,RETURN(0)),~
IF(n<0,RETURN((-1)^(1-n)*fibonacci(-n))),~
LOOP(~
IF(n=0,exit),~
b:=APPEND(b,[MOD(n,2)]),~
n:=FLOOR(n,2),~
i:=i+1),~
i:=i-2,~
LOOP(~
IF(i<1,exit),~
s1:=f2^2,~
s2:=2*f2*f1,~
f1:=s1+f1^2,~
f2:=s1+s2,~
IF(b SUB i=1,PROG(~
s3:=f2+f1,~
f1:=f2,~
f2:=s3)),~
i:=i-1),~
RETURN(f2))

fibonacci(754966)

16342705823785353270544771916388648463196561563760910050296708513979272567741~
43724504288069233998207285821600918504532636469781895967378743833777781533554~
68587366328397236472590482995176947342450055119385564253854189348555236456510~
21658143375137866489068225857415714283750680336019311001502874887334170820611~
87447594737014294691609299576300174395148806737892133279695428410553579490199~
[...........................................................................]
55677286747819881221042623317019498707011392469581831144127314327775950115516~
66307631754422426183851325743889837395685253670657527332664531789227161205493~
38948461237369042400983149645380944643650097854168013199063373451377723250481~
32665024743886228215643500207159774940467921701737458241175074481684216816053~
93966598257955927745328385221998619641487903876941722496899865956086017988915~
330863

Clearly the problem is not one of the algorithm per se.

Martin.

plouffe · Guest

I agree with that. There is range where the
functions doesn>t work : from 754966 to 755019.
It is certainly not related to the algorithm. I
scanned the other values beyond 755019, it seems
fine up to 800000, fibonacci(1000000) takes less
than 1 second to compute.

Simon Plouffe

Axel Vogt · Guest

clicliclic@freenet.de wrote:
[quote]Axel Vogt schrieb:
It is located in the last step of the loop for i=0, but not
through b[0] (what I guessed first), may be an interfacing
problem with GMP which is (possibly) used below Maple here.

Are you referring to the second loop (the loop with descending i)? In
that case I would suspect some spurious memory allocation problem as
f1, f2, s1, s2, s3 are growing to around 160k digits. Here is a
(slightly simplified) Derive 6.10 equivalent of the Maple procedure:

fibonacci(n,i:=1,b:=[],f1:=0,f2:=1,s1,s2,s3):=PROG(~
IF(NOT(INTEGER?(n)),RETURN("argument must be an integer")),~
IF(n=0,RETURN(0)),~
IF(n<0,RETURN((-1)^(1-n)*fibonacci(-n))),~
LOOP(~
IF(n=0,exit),~
b:=APPEND(b,[MOD(n,2)]),~
n:=FLOOR(n,2),~
i:=i+1),~
i:=i-2,~
LOOP(~
IF(i<1,exit),~
s1:=f2^2,~
s2:=2*f2*f1,~
f1:=s1+f1^2,~
f2:=s1+s2,~
IF(b SUB i=1,PROG(~
s3:=f2+f1,~
f1:=f2,~
f2:=s3)),~
i:=i-1),~
RETURN(f2))

fibonacci(754966)

16342705823785353270544771916388648463196561563760910050296708513979272567741~
43724504288069233998207285821600918504532636469781895967378743833777781533554~
68587366328397236472590482995176947342450055119385564253854189348555236456510~
21658143375137866489068225857415714283750680336019311001502874887334170820611~
87447594737014294691609299576300174395148806737892133279695428410553579490199~
[...........................................................................]
55677286747819881221042623317019498707011392469581831144127314327775950115516~
66307631754422426183851325743889837395685253670657527332664531789227161205493~
38948461237369042400983149645380944643650097854168013199063373451377723250481~
32665024743886228215643500207159774940467921701737458241175074481684216816053~
93966598257955927745328385221998619641487903876941722496899865956086017988915~
330863

Clearly the problem is not one of the algorithm per se.

Martin.
[/quote]
Yes, the 2nd loop (the 1st loop is some binary decomposition) and as
that code is identical with former versions and works on a MAC (see
G A Edgar) it is may be a compilation / memory error in creating the
WIN version. The size is not a problem per se.

One can isolate it as the last loop index (storing the constants
and executing in a separate sheet - bang ...), I posted it in that
form MaplePrimes as problem

ralphwallace1935@gmail.co · Guest

On Jul 12, 5:38 am, plouffe <simon.plou...@gmail.com> wrote:
[quote]Hello,

Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

...but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.

Simon Plouffe
[/quote]
Maple V ver 5,Maple 7.00 and Maple 10.03 work, so I suppect a garbage
collection bug.
Ralph

Bernd Strieder · Guest

Hello,

plouffe wrote:

[quote]Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

...but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.
[/quote]
I can reproduce the error under Linux using Maple 12, somewhat.
It crashes after 5 calls with stack limit reached.

Changing the stack limit (ulimit -H -s 16384 and ulimit -H -s 16384)
seem to provoke the crash after 2 calls of the range 755015 and up. I
have no idea. Other numbers over 20000000 seem to work, taking hundreds
of MB of RAM, but that range seems to be mysterious.

Bernd Strieder

Axel Vogt · Guest

plouffe wrote:
[quote]Hello,

Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

...but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.

Simon Plouffe
[/quote]
It got noted at Maple,
http://www.mapleprimes.com/forum/maple12gmpproblem#comment-18287

Dr. David Kirkby · Guest

On Jul 12, 11:38 am, plouffe <simon.plou...@gmail.com> wrote:
[quote]Hello,

Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

...but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.

Simon Plouffe
[/quote]

If you need the result, and don>t want to go to the expense of buying
software, Sage computes it almost instantly.

Dave

Michael Press · Guest

In article
<82af1e72-33b3-4117-a7a2-135f24e10ac4@k13g2000hse.googlegroups.com>,
"Dr. David Kirkby" <david.kirkby@onetel.net> wrote:

[quote]On Jul 12, 11:38 am, plouffe <simon.plou...@gmail.com> wrote:
Hello,

Maple has an implementation of Fibonacci numbers which is
not bad, you type fibonacci(1000000); and the answer comes
right away.

...but why is it that fibonacci(754966); makes the mserver to
crash ???

I am using a pentium E6400, 2.13 Ghertz, 2 gigs ram and Maple12.

Can someone try this on his system ?

ps : you need to load with(combinat); before to load the program.

Simon Plouffe

If you need the result, and don>t want to go to the expense of buying
software, Sage computes it almost instantly.
[/quote]
The following identity for the Fibonacci numbers is well known.
F_{n-1}F_{m} + F_{n}F_{m+1} = F_{m+n}

Set n = m+1
(F_{m})^2 + (F_{m+1})^2 = F_{2m+1}

Suppose we know F_{k-1}, F_{k},F_{k+1}. Then

F_{2k-1} = (F_{k-1})^2 + (F_{k})^2
F_{2k} = (F_{k+1})^2 - (F_{k-1})^2
F_{2k+1} = (F_{k})^2 + (F_{k+1})^2

If we want to know F_{n} for large n, we can find it
without iterating up from F_1.

(20)_10 = (10100)_2

F_4 = 3
F_5 = 5
F_6 = 8
F_9 = 3^2 + 5^2 = 34
F_10 = 8^2 - 3^2 = 55
F_11 = 5^2 + 8^2 = 89
F_19 = 34^2 + 55^2 = 4181
F_20 = 89^2 - 34^2 = 6765
F_21 = 55^2 + 89^2 = 10946

There are formulae that accomplish each step with
only 2 multiplications, rather than 3 squares.

--
Michael Press


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Math - Symbolic Forum	Goto page 1, 2 Next
Page 1 of 2