Page 1 of 1
Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 11:06 am
by Neurox66
Hi,
I've wrote this function for calculate the Fibonacci numbers.
Code: Select all
function Fibonacci pNum
put 0 into tN
put 0 into tF1
put 0 into tF2
repeat with tX = 1 to pNum
put tF1 + tF2 into tN
if tN = 0 then put 1 into tN
put tF2 into tF1
put tN into tF2
end repeat
return tF2
end Fibonacci
The strange result is from number 79 and up.
Example
Fibonacci(77) is 5527939700884757
Fibonacci(78) is 8944394323791464
but Fibonacci(79) return 14472334024676220
and is wrong because the correct number is
14472334024676221
Is it a LiveCode problem?
Any Hint?
Thanks,
Paolo
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 2:28 pm
by Mark
Hi Paolo,
Beyond 15 digits, LiveCode isn't a reliable calculator.
Kind regards,
Mark
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 2:31 pm
by [-hh]
..........
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 2:34 pm
by Mark
Hi Hermann,
I hope Paolo doesn't mind me asking this. What strikes me is your "approx". Do you know of a way to determine the exact threshold? I've been looking for that for ages.
Kind regards,
Mark
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 3:08 pm
by dunbarx
Hi.
You can always roll your own. I used to do that 40 years ago.
But I wrote a function, I would say, 20 years ago, that adds numbers of any length by bypassing the native "add" command. It was not hard to do, and is easy to understand:
Code: Select all
function longAdd arg1,arg2
put 0 into carry
put abs(the length of arg1-the length of arg2) into numzeros
repeat numzeros
put "0" after leadingZeros
end repeat
if the length of arg1 >= the length of arg2 then
put the length of arg1 into index
put leadingZeros before arg2
else
put the length of arg2 into index
put leadingZeros before arg1
end if
repeat with y = index down to 1
put char y of arg1 + char y of arg2 + carry into temp
if char y of arg1 + char y of arg2 + carry > 9 then put 1 into carry else put 0 into carry
put last char of temp before accum
end repeat
if carry = 1 then put "1" before accum
return accum
end longAdd
If you try this with your last two Fibonacci numbers, it will give the correct result. You can certainly incorporate it into a general Fib generator.
Craig Newman
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 4:27 pm
by [-hh]
..........
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 9:23 pm
by dunbarx
Hermann.
I wrote this the same day. I think it is valid, but would defer to you if you find it has logical lapses. You need to have that longAdd function handy:
Code: Select all
function longMult arg1,arg2
put the number of chars of arg1 into arg1Length
put the number of chars of arg2 into arg2Length
put 0 into theProduct
repeat with u = the number of chars of arg2 down to 1
put 10 ^ (arg2Length - u) into uTensPlace
repeat with y = the number of chars of arg1 down to 1
put 10 ^ (arg1Length - y) into yTensPlace
put char y of arg1 * yTensPlace * char u of arg2 * uTensPlace & return after accum
end repeat
end repeat
repeat with y = 1 to the number of lines of accum
put longAdd(line y of accum,theProduct) into theProduct
end repeat
return theProduct
end longMult
Craig
Re: Strange result with Fibonacci Function
Posted: Mon Dec 02, 2013 10:27 pm
by dunbarx
Hermann.
I went onto a large number multiplication site and tested a few numbers. My gadget seems to work fine up until a 24 digit product comes up. Not sure why this should be so, since I was dealing with, as you say, string manipulation, and it seems to work fine up to that point. Still way past the 15 digits available natively. I assume some limit is broken in the machine, though it just might be some problem with the gadget. Any ideas?
Craig
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 12:16 am
by [-hh]
..........
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 2:25 am
by [-hh]
..........
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 6:42 am
by dunbarx
Hermann.
Ah, I see.
And I see there is a way to do this with properly padded strings. Lots of 0's needed, but those are cheap.
Craig
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 7:59 am
by Neurox66
Hi,
thanks to all for the answers,
I've read many interesting things.
@Hermann
With new function the time changes from 2 to 5 milliseconds on iMac 27" late 2012 at 2,9Ghz iCore5 and 8GB ram
I've tested again but the problem remains.
Even with the new function Fibonacci(79) ends up with 20 and not 21.
That is the modified code:
Code: Select all
on mouseUp
put the millisecs into tTime
set the text of field "fldResult" to Fibonacci(79)
set the text of field "fldMSG" to the millisecs - tTime
end mouseUp
function Fibonacci pNum
put 0 into tN
put 0 into tF1
put 0 into tF2
repeat with tX = 1 to pNum
put longAdd(tF1 + tF2) into tN
if tN = 0 then put 1 into tN
put tF2 into tF1
put tN into tF2
end repeat
return tF2
end Fibonacci
//---------------------//
function longAdd arg1,arg2
put 0 into carry
put abs(the length of arg1-the length of arg2) into numzeros
repeat numzeros
put "0" after leadingZeros
end repeat
if the length of arg1 >= the length of arg2 then
put the length of arg1 into index
put leadingZeros before arg2
else
put the length of arg2 into index
put leadingZeros before arg1
end if
repeat with y = index down to 1
put char y of arg1 + char y of arg2 + carry into temp
if char y of arg1 + char y of arg2 + carry > 9 then put 1 into carry else put 0 into carry
put last char of temp before accum
end repeat
if carry = 1 then put "1" before accum
return accum
end longAdd
Paolo
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 8:43 am
by Neurox66
Dear Mark,
Mark wrote:Hi Paolo,
Beyond 15 digits, LiveCode isn't a reliable calculator.
Mark
It's not a good answer
Because I'll expect from a powerfull (and expensive) programming language make a perfect and properly calculations from 1 to 300 digits!
I've a downloaded a KBasic and I've rewrite the Fibonacci and...
the result is correct!
again
I've a downloaded a GLBasic and I've rewrite the Fibonacci and...
the result is correct!
again
I've a downloaded a FutureBasic and I've rewrite the Fibonacci and...
the result is correct!
and xCode too
Paolo
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 10:06 am
by [-hh]
..........
Re: Strange result with Fibonacci Function
Posted: Tue Dec 03, 2013 10:18 am
by Neurox66
Hi Hermann,
argghhh
Yes you right
Thanks,
Paolo