Strange result with Fibonacci Function

Anything beyond the basics in using the LiveCode language. Share your handlers, functions and magic here.

Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller, robinmiller

Post Reply
Neurox66
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 120
Joined: Tue May 22, 2012 1:57 pm
Contact:

Strange result with Fibonacci Function

Post by Neurox66 » Mon Dec 02, 2013 11:06 am

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
Paolo Borzini | paolo@borzini.it
The WhiteFly Software | www.thewhitefly.it
Service on line for printers | www.4pellicole.it

Mark
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 5150
Joined: Thu Feb 23, 2006 9:24 pm
Contact:

Re: Strange result with Fibonacci Function

Post by Mark » Mon Dec 02, 2013 2:28 pm

Hi Paolo,

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

Kind regards,

Mark
The biggest LiveCode group on Facebook: https://www.facebook.com/groups/livecode.developers
The book "Programming LiveCode for the Real Beginner"! Get it here! http://tinyurl.com/book-livecode

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: Strange result with Fibonacci Function

Post by [-hh] » Mon Dec 02, 2013 2:31 pm

..........
Last edited by [-hh] on Wed Aug 13, 2014 11:40 am, edited 2 times in total.
shiftLock happens

Mark
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 5150
Joined: Thu Feb 23, 2006 9:24 pm
Contact:

Re: Strange result with Fibonacci Function

Post by Mark » Mon Dec 02, 2013 2:34 pm

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
The biggest LiveCode group on Facebook: https://www.facebook.com/groups/livecode.developers
The book "Programming LiveCode for the Real Beginner"! Get it here! http://tinyurl.com/book-livecode

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10354
Joined: Wed May 06, 2009 2:28 pm

Re: Strange result with Fibonacci Function

Post by dunbarx » Mon Dec 02, 2013 3:08 pm

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]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: Strange result with Fibonacci Function

Post by [-hh] » Mon Dec 02, 2013 4:27 pm

..........
Last edited by [-hh] on Wed Aug 13, 2014 11:40 am, edited 1 time in total.
shiftLock happens

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10354
Joined: Wed May 06, 2009 2:28 pm

Re: Strange result with Fibonacci Function

Post by dunbarx » Mon Dec 02, 2013 9:23 pm

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
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10354
Joined: Wed May 06, 2009 2:28 pm

Re: Strange result with Fibonacci Function

Post by dunbarx » Mon Dec 02, 2013 10:27 pm

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]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: Strange result with Fibonacci Function

Post by [-hh] » Tue Dec 03, 2013 12:16 am

..........
Last edited by [-hh] on Wed Aug 13, 2014 11:40 am, edited 1 time in total.
shiftLock happens

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: Strange result with Fibonacci Function

Post by [-hh] » Tue Dec 03, 2013 2:25 am

..........
Last edited by [-hh] on Wed Aug 13, 2014 11:40 am, edited 1 time in total.
shiftLock happens

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 10354
Joined: Wed May 06, 2009 2:28 pm

Re: Strange result with Fibonacci Function

Post by dunbarx » Tue Dec 03, 2013 6:42 am

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
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 120
Joined: Tue May 22, 2012 1:57 pm
Contact:

Re: Strange result with Fibonacci Function

Post by Neurox66 » Tue Dec 03, 2013 7:59 am

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
Paolo Borzini | paolo@borzini.it
The WhiteFly Software | www.thewhitefly.it
Service on line for printers | www.4pellicole.it

Neurox66
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 120
Joined: Tue May 22, 2012 1:57 pm
Contact:

Re: Strange result with Fibonacci Function

Post by Neurox66 » Tue Dec 03, 2013 8:43 am

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
Paolo Borzini | paolo@borzini.it
The WhiteFly Software | www.thewhitefly.it
Service on line for printers | www.4pellicole.it

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm

Re: Strange result with Fibonacci Function

Post by [-hh] » Tue Dec 03, 2013 10:06 am

..........
Last edited by [-hh] on Wed Aug 13, 2014 11:39 am, edited 1 time in total.
shiftLock happens

Neurox66
Livecode Opensource Backer
Livecode Opensource Backer
Posts: 120
Joined: Tue May 22, 2012 1:57 pm
Contact:

Re: Strange result with Fibonacci Function

Post by Neurox66 » Tue Dec 03, 2013 10:18 am

Hi Hermann,
argghhh :oops:
Yes you right :D

Thanks,
Paolo
Paolo Borzini | paolo@borzini.it
The WhiteFly Software | www.thewhitefly.it
Service on line for printers | www.4pellicole.it

Post Reply