Lack of overflow check?

[Hello12345]

Tested out a linear fibonacci program and noticed that there is an overflow at 1476 which does not get treated as i would expect, it gives you a negative number.

if i then try to compute anything above 1476 then it return the wrong number in the computation.

$n = InputBox("Enter Number","",""," M","-1","-1","-1","-1")
MsgBox(0,"Fibonacci for"&" "&$n ,Fib ($n))
Func Fib ($n)
   $prev = 0
   $next = 1
    For $i=1 to $n
        $prev = $next - $prev
        $next = $prev + $next               
    Next
   return ($prev) 
EndFunc

Edited June 11, 2006 by Hello12345

[Wus]

I dont think thats a bug.. your right its called overflow.

I think it happens before that though... theres no way that your calculating Fib(1400) or greater...

the Fib(91) thru Fib(100) per your program...

4660046610375530309

7540113804746346429

-6246583658587674878

1293530146158671551

-4953053512429003327

-3659523366270331776

-8612576878699335103

6174643828739884737

-2437933049959450366

3736710778780434371

Im assuming your doing thins because you like math... this is the Fibbonacci series!!! it grows pretty damn fast. If you want to do this with accuracy check out the BigInteger class in Java. Hell if you want I can post the code... or you can google it.

Edited June 11, 2006 by Wus

[Valik]

Wus is correct, this is perfectly normal behavior. The maximum size of an integer AutoIt can use is 64-bits which has a maximum value of 9223372036854775807. Anything above that is going to overflow. If you need something larger than __int64, you'll need to implement your own number "type" with AutoIt instead of relying on AutoIt's internal storage. This, of course, will not be very efficient.

[nfwu]

I am bored, so I give a shot a really big numbers: (I know that 100000000000000000 is 1 less 0 than 1000000000000000000, k?)

$n = InputBox("Enter Number","",""," M","-1","-1","-1","-1")
MsgBox(0,"Fibonacci for"&" "&$n ,Fib ($n))
Func Fib ($n)
   $prev = 0
   $prev_big = 0
   $next = 1
   $next_big = 0
    For $i=1 to $n
        $prev = $next - $prev
        $prev_big = $next_big - $prev_big
        If $prev >= 100000000000000000 Then 
           $prev_big += Mod($prev, 100000000000000000)
           $prev = Int($prev/100000000000000000)
        EndIf
        If $prev_big < 0 Then
           $prev -= $prev_big * 100000000000000000
           $prev_big = 0
        EndIf
        $next = $prev + $next            
        $next_big = $prev_big + $next_big   
        If $next >= 100000000000000000 Then 
           $next_big += Mod($next, 100000000000000000)
           $next = Int($next/100000000000000000)
        EndIf        
    Next
   return $prev_big & "" & $prev
EndFunc

Not tested, but you should get the idea.

#)

[Wus]

If you really wanted to waste time and effort you could use arrays to hold numbers... devise your own addition routines. Then you'd have much much larger storage.

like character strings

i.e.

5984 is stored as

$a[0] = 5

$a[1] = 9

$a[2] = 8

$a[3] = 4

Of course then you run into the problem of not knowing the maximum size... but you could just make your array large enough for the maximum possible for your operation... maybe I'll write this set of functions for kicks.

[gamerman2360]

If you really wanted to waste time and effort you could use arrays to hold numbers... devise your own addition routines. Then you'd have much much larger storage.

like character strings

i.e.

5984 is stored as

$a[0] = 5

$a[1] = 9

$a[2] = 8

$a[3] = 4

Of course then you run into the problem of not knowing the maximum size... but you could just make your array large enough for the maximum possible for your operation... maybe I'll write this set of functions for kicks.

You might want ot turn that around:

$a[0] = 4

$a[1] = 8

$a[2] = 9

$a[3] = 5

Otherwise you would be moving them around everytime it went up to another placeholder.

Edited June 11, 2006 by gamerman2360

[Wus]

Well I was really bored today so I hacked together an arbitrary precision integer data type (well really just a special array). Its not documented and pretty hideous code but it works and I found the 1000th Fib number

Fib(1000) = +4346655768693745643568852767504062580256466051737178040248172908953655541794905 189040387984007925516929592259308032263477520968962323987332247116164299644090653318793829 8969649928516003704476137795166849228875

I will most likely clean the code and a multiply and a divide function as well. Alond with documentation.

Now the functions are just

_intToBigInteger( [input integer here] )

AND

_addBigIntegers( [bigint], [bigint]

The BigInteger is defined as an array with the zeroth element as either "+" or "-" and the rest of the elements as the digits of a number (base 10) with the ones in index one the tens in index 2 and so on.

To test the Fib(1000) just run the attatched au3 and a msgbox will appear.

There is also an attached file that has the first 1000 fibbonacci numbers in it as calculated by my script.

BTW yeh you were right gamerman... I duno what I was thinking when i typed that.

Edited June 14, 2006 by Wus

[Richard Robertson]

I'm going to take a look at this code. I was planning on developing a 128 bit integer and this may help.

~Reading code~

Nevermind, this is rather hideous. (no offense)

I'll probably never make it before I need it.

[Wus]

Well yeh, the code hideous. I never claimed it was good, but the underlying concept of an array representation of a number isnt horrible. Ill repost when I clean it up, and I think that alot of things will consolidate. Just curious what method were you going to use for a 128 bit integer?

BTW the code may be ugly but it works just perfectly (minus the performance kickbacks).

[Valik]

I'm going to take a look at this code. I was planning on developing a 128 bit integer and this may help.

~Reading code~

Nevermind, this is rather hideous. (no offense)

I'll probably never make it before I need it.

I think you're going to find that implementing a number type in AutoIt is going to look hideous no matter how it's done.

Edit: Fixed typo.

Edited June 12, 2006 by Valik

[Wus]

I will be overhauling the multiply function due to horrible inefficiency. It does work though (I believe).

If possible I will add a _divBigIntegers() function too.

FYI though it takes forever and a day to find 100! with my code, in java you can use the real biginteger class and it will output 10000! in less than 2 seconds.

Edited June 14, 2006 by Wus

[Richard Robertson]

I wasn't going to write a 128 bit integer for AutoIt. I was going to write it in C++ or .Net.

It would be an array of 16 bytes that I would work with as a single block of memory. It will be hard, which is why i most likely won't make it before I need a number as big as has been listed in my signiture.

The number listed in my signiture is what calc.exe gave me from 2 ^ 128. My integer will have a very large integral precision. It can't get as big as a double, but it is much more precise.

[Wus]

An update of the code... much more efficient. I will post further updates in the scrips and scraps seeing how this isnt really the place anymore. Added better function descriptions and added simple error checking too.

ArbitraryPrecisionInt.au3

[Hello12345]

@ all

thanks for the comments.

I appreciate all the help.

thanks again