The Fibonacci series

[ganache]

This is a program for printing Fibonacci series.

Code: Select all

 Dim  As Integer a =-1, b=1, c=0
 Dim  As Integer i, n=45
 print
 print tab(1);"No.";tab(17);"Fibonacci "
 print "-------------------------"
 for i=0 to n
 c = a+b
 a = b
 b = c
 print i,using "##########";b
 next i
 Sleep
 End

 ' Program shows first 45 terms of Fibonacci series.
 ' For bigger values of n, you have to change data type.

[MrSwiss]

Jep, and below we are doing the same, somewhat better 'styled'. (better readability)
The series goes up to 60 now, also:

Code: Select all

' Program shows first 60 terms of Fibonacci series.

Dim As LongInt  a = -1, b = 1, c = 0, n = 60
Dim As String   title = "No.            Fibonacci"

Locate 2, 2     ' start printing at: 2nd line, 2nd column
Print title     ' title
Print String(Len(title) + 2, "-")   ' title underline (add 2: 1 before/1 after) 
print           ' a empty line

For i As UInteger = 0 To n
    c = a + b
    a = b
    b = c
    Print i, Using "#############"; b
Next

Sleep : End 0   ' end is not mandatory (after sleep it finishes anyway!)

Btw: Important comments: always 'on top' because:
you'll never know, 'how long' the code will be (starting a project).

[srvaldez]

here's mine

Code: Select all

'prints the first 116 Fibonacci numbers 
'http://www.flyingcoloursmaths.co.uk/ask-uncle-colin-is-the-fibonacci-series-witchcraft/
#include once "gmp.bi"

dim as __mpf_struct fib
dim as string s
dim as zstring ptr buf=allocate(3000)
dim as integer i, j

mpf_init2(@fib,9600)
print "calculate the first 116 fibonnaci numbers"
s=string(23,"9")+"8"+string(24,"9")
mpf_set_str(@fib, s, 10)
mpf_ui_div (@fib, 1, @fib) 'fib=1/fib
gmp_sprintf(buf, "%2885.2880Ff", @fib)
s=*buf
s=mid(s,6)

j=1
for i=1 to 58
	print mid(s,j,24),mid(s,j+24,24)
	j+=48
next
deallocate(buf)
mpf_clear(@fib)

[dodicat]

Data type string:
original range (45) times 10.
The code is a bit longer due to string addition.
But the same in principle.
The windows console should scroll all.
Don't know about Linux though.

Code: Select all

'fibonacci by data type -- string.
'following Wiki format
'I.e.
'The first few Fibonacci numbers Fn for n = 0, 1, 2, …
'F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	 F18  F19  F20
'0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597 2584 4181 6765


Function fibonacci(n As long) As String
    static As Ubyte Qmod(0 To 19)={48,49,50,51,52,53,54,55,56,57,48,49,50,51,52,53,54,55,56,57}
    static As Ubyte Qbool(0 To 19)={0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1}
    Dim As Ubyte addup,addcarry
    Dim As Long diff,n_,LL
    if n=0 then return "0"
    if n=1 or n=2 then return "1"
    if n=3 then
        return "2"
        else
    Dim As String sl="1",l="2",term
    For x As long= 1 To n-3
        LL=Len(l)
        diff=-(LL<>Len(sl))
        term="0"+l
        addcarry=0
        For n_=LL-1 To diff Step -1
            addup=sl[n_-diff]+l[n_]-96
            term[n_+1]=Qmod(addup+addcarry)
            addcarry=Qbool(addup+addcarry)
        Next n_
        If addcarry=0 Then  term=Ltrim(term,"0"):Goto skip
        If n_=-1      Then term[0]=addcarry+48  :Goto skip
        For n_=n_ To 0 Step -1
            addup=l[n_]-48
            term[n_+1]=Qmod(addup+addcarry)
            addcarry=Qbool(addup+addcarry)
            If addcarry=0 Then Exit For
        Next n_
        term[0]=addcarry+48
       if addcarry=0 then term=Ltrim(term,"0")
        skip:
        sl=l
        l=term
    Next x
    Function =term
    end if
End Function

width 130,500
dim as string s
for n as ulong=0 to 450
    s=s+ "F"&n & string(12-len(str(n))," ") &fibonacci(n) &!"\n" 'position + gap +fibonacci number + new line
   'print "F";n, fibonacci(n)
next
print s
sleep 

[ganache]

Very nice dodicat!

[Makoto WATANABE]

Dear srvaldez
Dear dodicat

Thank you for posting interesting programs all the time.
I am planning to introduce your programs to Japanese people on my website.

[integer]

OLD SCHOOL
Middle school method; Mrs. Brickles (8th grade teacher) & graph paper allowed me to reach 40 digits or someting.
Three of us students had the same number.
[This was prior to PC's in the class room.]

Code: Select all

'' FibonacciNumeracci.bas

'' F(4778) has 999 digits

DECLARE SUB NextFibo()
DECLARE SUB DispFibo()

/'
   F_(n) = F_(n-1) + f_(n-2)
'/
   
'' byte allows 127 digits
'' ubyte allows 255 digits
'' short can hit 32768 digits, BUT the array dim must be changed

   dim shared as short f0(1000)
   dim shared as short f1(1000)
   dim shared as short f2(1000)
   dim as byte a
   dim as short fnum
   
   f0(0)=1     '' indicator for the numbers of digits in this number
   f0(1)=0     '' 1st digit in this Fibonacci number
   
   f1(0)=1     '' the number of digits in this Fibonacci number
   f1(1)=1     '' the value of the lowest (or first) digit this number
   
   f2(0)=1     '' the number of digits in this Fibonacci number
   f2(1)=1     '' the value of the lowest (or first) digit this number

   fnum = 1    '' fibonum0 = 0; fibonum1 = 1; fibonum2 = 1
   DO
      NextFibo()
      fnum += 1
      print "F#";fnum;", has "; f2(0);" digits: ";  
      DispFibo()
      'if (fnum mod 10)=0 then a = getkey
      'if (fnum > 997 ) then a = getkey
      'if f2(0)>998 then exit do
      a = getkey
   loop until a=27
   print ":o)"
   a = getkey

'' calc next Fibonacci number in sequence: F(n+1)= f(n)+f(n-1)
SUB NextFibo()
   dim as short j, k, carry
   j=f1(0)                    '' max # of digits to sum
   carry = 0
   for k = 1 to j
      f2(k) = f1(k)+f0(k)+carry
      carry = 0
      if f2(k) > 9 then 
         carry = 1
         f2(k) -= 10
      end if
   next k
   if carry then j+=1 : f2(j)=1 end if
   f2(0) = j
   for k = 0 to j       '' shift f1 --> f0 and f2 --> f1
      f0(k) = f1(k)
      f1(k) = f2(k)
   next k
END SUB


SUB DispFibo()
   dim as short d = f2(0)
   while d
      print using"#";f2(d);
      d -= 1
   wend
   print
end sub

it is speedy, if you do not print the intermediate values.

[srvaldez]

here's generalized version of my code above

Code: Select all

/'
Following is text snippet from the text regarding number of bits required for nth Fibonacci number. It is reasonable to treat addition as a single computer step if small numbers are being added, 32-bit numbers say. But the nth Fibonacci number is about 0.694n bits long, and this can far exceed 32 as n grows.Mar 9, 2011
algorithm - about number of bits required for Fibonacci number - from Stack Overflow
https://stackoverflow.com/questions/5248219/about-number-of-bits-required-for-fibonacci-number
'/

'also see http://www.flyingcoloursmaths.co.uk/ask-uncle-colin-is-the-fibonacci-series-witchcraft/
#include once "gmp.bi"

dim as __mpf_struct fib
dim as string s
dim as integer i, j, n, nd=16 'number of digits per fibonacci number

n=4.792529188683721*nd+1
while bit(n,0)
	nd+=1
	n=4.792529188683721*nd+1
wend
dim as zstring ptr buf=allocate((n+4)*nd+10)

mpf_init2(@fib,4*n*nd)
print "calculate the first ";n;" fibonnaci numbers"
s=string(nd-1,"9")+"8"+string(nd,"9")
mpf_set_str(@fib, s, 10)
mpf_ui_div (@fib, 1, @fib) 'fib=1/fib
s="%"+str((n+4)*nd+5)+"."+str((n+4)*nd)+"Ff"
gmp_sprintf(buf, s, @fib)
s=*buf
s=mid(s,6)

j=1
for i=1 to n\2
	print mid(s,j,nd),mid(s,j+nd,nd)
	j+=nd+nd
next
deallocate(buf)
mpf_clear(@fib)
print "The number of fibonacci numbers is"; n
print "The number of digits per number is"; nd
sleep