Strange result with Fibonacci Function

[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

[Mark]

Hi Paolo,

Beyond 15 digits, LiveCode isn't a reliable calculator.

Kind regards,

Mark

[[-hh]]

..........

[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

[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

[[-hh]]

..........

[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

[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

[[-hh]]

..........

[[-hh]]

..........

[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

[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

[Neurox66]

Dear Mark,

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

[[-hh]]

..........

[Neurox66]

Hi Hermann,
argghhh
Yes you right

Thanks,
Paolo