Why does fibonacci sequence script stop making sense at 92nd iteration?


 
Thread Tools Search this Thread
Top Forums UNIX for Dummies Questions & Answers Why does fibonacci sequence script stop making sense at 92nd iteration?
# 1  
Old 04-25-2010
Why does fibonacci sequence script stop making sense at 92nd iteration?

So, Just for practice, I wrote a simple fibonacci sequence script in bash.

Code:
(03:08:02\[D@DeCoBox15)
[~]$ cat fib
#!/usr/bin/bash				

ret ()
{
        echo -ne "\n"
        sleep .5
}


a=1
b=2
echo -n $a      #1      A
ret
echo -n $b      #2      B
ret

while true
do
        c=$(($a+$b))
        echo -n $c      #3      C
        ret
        a=$(($c+$b))
        echo -ne $a     #5      A
        ret
        b=$(($c+$a))
        echo -ne $b     #8      B
        ret
done

(03:05:20\[D@DeCoBox15)
[~]$ ./fib|head -15|nl
     1  1
     2  2
     3  3
     4  5
     5  8
     6  13
     7  21
     8  34
     9  55
    10  89
    11  144
    12  233
    13  377
    14  610
    15  987

It works, but one thing I've noticed is that when ever it gets to the 92nd iteration, it starts throwing out weird numbers that don't make sense:

Code:
(03:05:05\[D@DeCoBox15)
[~]$ ./fib|head -92|nl|tail -1
    92  -6246583658587674878

I've tested it in cygwin, on a solaris box at work, and on a rhel box at work, and all show the same thing when it hits 92.

I assume that it has something to do with the maximum value that can be saved in memory or something like that...but I'm not remotely a computer scientist, just a humble admin.

So can anyone explain this a bit for me?
# 2  
Old 04-25-2010
This is because of the numerican expression out of range.

you can try the below perl script. This perl script uses the bigInt

Code:
#!/usr/bin/perl

#--------------------------------------------------------------------#
#Fibonacci Generator
#       Date Written:   22-Jul-2001 10:12:09 AM
#       Last Modified:  13-Aug-2001 10:06:30 AM
#       Author:         Kurt Kincaid
#
#       This is free software and may be redistributed under the
#       same terms as Perl itself.
#--------------------------------------------------------------------#

use Getopt::Std;
use Math::BigInt;

$| = 1;
$VERSION = "1.2";
$x = Math::BigInt->new(1);
$y = Math::BigInt->new(2);

getopts("ch");

$\= $opt_c ? "\n" : " ";

if ( $opt_h ) {
    print <<END;
Fibonacci Generator v$VERSION
Usage: $0 [-ch] [number]
-c\tPrint output in a single column (default is rows)
-h\tPrint help text (what you're reading now)

    Include how many numbers in the sequence you want, 
    otherwise it defaults to 100.
END
    exit;
}

my $stop = shift || 100;

print "$x\n";
print "$y\n";

for ( 3 .. $stop ) {
    ( $x, $y ) = ( $y, $x+$y );
    print "$y\n";

}

# 3  
Old 04-25-2010
Quote:
Originally Posted by itkamaraj
This is because of the numerican expression out of range.
Not to sound ungrateful...but that doesn't mean anything to me. I'm not doing this to achieve anything, just for practice. So I'm trying to understand why, when I do it in bash, I get the results that I do.

I'm not really looking for alternative languages this could be done in (though I welcome any critique on how I could have done my way better)...I just want to understand a bit more.
# 4  
Old 04-25-2010
This is what the output looks like if you use ksh93 instead of bash:
Code:
 92  1.220017e+19

# 5  
Old 04-26-2010
The answer to your question: you blew past the largest number that bash can handle.
bash uses integer datatypes for internal arithmetic operations. They only count up so far.

try:
Code:
> getconf LONG_MAX
2147483647

On the system I ran the getconf command the largest positive integer my shell can deal with is: 2147483647
getconf is a good command for a sysadmin to know BTW.
# 6  
Old 04-26-2010
So if its just for fun, write your own double precision, you know the rules 5+6 = 1 carry 1.
Just do the split at 9 decimal digits. Print the result with no spaces between the two values.
# 7  
Old 04-26-2010
Quote:
Originally Posted by DeCoTwc
Not to sound ungrateful...but that doesn't mean anything to me. I'm not doing this to achieve anything, just for practice. So I'm trying to understand why, when I do it in bash, I get the results that I do.
It's odd that you'd get those results in bash. It's the one bourne shell I've found that can handle really, really, really huge integer values. (not float, integer!) At least in my version. What version do you have?
Code:
$ echo $((2147483647*2147483647))
4611686014132420609
$ bash --version
GNU bash, version 4.0.35(2)-release (i686-pc-linux-gnu)
Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>

This is free software; you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

and yes, that's on a 32-bit system. I"ve seen bash 3.x (and maybe 2.x) handle enormous ints too. But I suppose the 93rd fibbonaci number might exceed even that. Simply put, you're running out of bits to represent numbers with, causing the number to wrap around past -MAX. With a signed 8-bit number, adding one to 127 gets you -128...

Last edited by Corona688; 04-26-2010 at 12:34 PM..
 
Login or Register to Ask a Question

Previous Thread | Next Thread

9 More Discussions You Might Find Interesting

1. Solaris

Beadm create -p on another pool - making sense of it

Hi all, I am trying out Solaris 11.3 Realize the option of -p when using beadm that i can actually create another boot environment on another pool. root@Unicorn6:~# beadm create -p mypool solaris-1 root@Unicorn6:~# beadm list -a BE/Dataset/Snapshot Flags... (1 Reply)
Discussion started by: javanoob
1 Replies

2. Programming

This Makes NO sense. I'm making a game and getting an error, need help.

Okay so I'm making a simple text based game that branches into different scenarios. By branching I mean branching off into whole different files with that part of the game in it. I got tired of working on scenario 1 so I'm working on scenario 2. As I get started and try to test it, I get an error... (1 Reply)
Discussion started by: lemonoid
1 Replies

3. Homework & Coursework Questions

program to find and print a Fibonacci sequence of numbers. --Errors

Use and complete the template provided. The entire template must be completed. If you don't, your post may be deleted! 1. The problem statement, all variables and given/known data: I am trying to convert a C language program over to Sparc Assembley and I am getting Undefined first referenced... (4 Replies)
Discussion started by: kenjiro310
4 Replies

4. Shell Programming and Scripting

howto stop loop iteration

I wonder how to stop further loop iterations when conditions gets false e.g. This file.txt contains the following structure : 1 2 3 4 5 6 7 8 9 10 How to stop iteration when if statement gets false ? for n in `cat file.txt` do if (( n<=5 )) (1 Reply)
Discussion started by: presul
1 Replies

5. Shell Programming and Scripting

Shell script to find the sum of first n Fibonacci numbers

pls give me the solution for this i need it for my exam pls pls pls Shell script to find the sum of first n Fibonacci numbers (1 Reply)
Discussion started by: Kshitija
1 Replies

6. UNIX for Dummies Questions & Answers

Need help making a start/stop script...

i have two separate scripts that work nicely to curl and generate two files.. one html and one txt so a total of four. When the script starts up i want it to: call and run shellscripta call and run shellscriptb sleep for about 40 seconds again run shellscripta again run shellscriptb check... (4 Replies)
Discussion started by: phpfreak
4 Replies

7. Solaris

Making sense of df -k & format verify output

I'm posting the output from two disks on my Solaris machine. The first part is the output from using the format command and then using the verify option on each disk. The last part is the output from my df -k command. I'm trying to match the partition to the filesystem/mount point. I'm assuming... (13 Replies)
Discussion started by: gonzotonka
13 Replies

8. Solaris

STOP A sequence

Hi, I have a sun sparc system. I don't have a sun keyboard, hence i connected a pc keyboard. I would like to know the "STOP A" equivalent command to be used on pc keyboard. Regards, Raja (4 Replies)
Discussion started by: RajaRC
4 Replies

9. UNIX for Advanced & Expert Users

Process calls - making sense of truss results

Can someone point me at resources for system calls? Specifically, I am trying to make sense of what I am seeing in a truss command. Thanks! (3 Replies)
Discussion started by: jpeery
3 Replies
Login or Register to Ask a Question