I wrote a simple program to display Fibonacci numbers to a 16x2 LCD screen.
Here is the loop portion:
void loop() {
int a = 0;
int b = 1;
for (int i = 0; i < 20; i += 1)
{
myDisplay.setCursor(0, 1);
myDisplay.print(a);
int c = a + b;
a = b;
b = c;
delay(analogRead(A0));
}
}
Clearly, this should display the first 19 Fibonacci numbers, and then start over at zero. But it doesn't. at its current setting (i < 20), it displays the first 19 numbers just fine, and then starts doing a weird digit increment thing. (starts at 131, then 1131, then 2131, and so on until it wraps, then repeats with the wrapped digits).
I'm so confused as to why. The first thing I do in the main loop is declare a and b as 0 and 1 respectively, what's going on here?
integers have a limited range, try to make the type uint32_t or even uit_64_t
Note your loop only goes to the 20th number
try this variation
//
// FILE: fibonacci.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.0.1
// PURPOSE: demo
//
// HISTORY:
uint32_t a = 0;
uint32_t b = 1;
int cnt = 0;
void setup()
{
Serial.begin(115200);
Serial.println(__FILE__);
}
void loop()
{
Serial.print(cnt++);
Serial.print("\t");
Serial.println(a);
uint32_t c = a + b;
a = b;
b = c;
delay(100);
}
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
17 1597
18 2584
19 4181
20 6765
21 10946
22 17711
23 28657
24 46368
25 75025
26 121393
27 196418
28 317811
29 514229
30 832040
31 1346269
32 2178309
33 3524578
34 5702887
35 9227465
36 14930352
37 24157817
38 39088169
39 63245986
40 102334155
41 165580141
42 267914296
43 433494437
44 701408733
45 1134903170
46 1836311903
47 2971215073
48 512559680
note for uint64_t you need to add 64 bit support for Serial.print.
OK as it is weekend, here a 64 bit version
//
// FILE: fibonacci.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.0.1
// PURPOSE: demo
//
// HISTORY:
uint64_t a = 0;
uint64_t b = 1;
int cnt = 0;
void setup()
{
Serial.begin(115200);
Serial.println(__FILE__);
}
void loop()
{
Serial.print(cnt++);
Serial.print('\t');
// 64 BIT PRINT
char s[28];
int idx = 0;
uint64_t t = a;
while (t > 0)
{
s[idx++] = (t % 10) + '0';
t = t / 10;
}
idx--;
while (idx >= 0)
{
Serial.print(s[idx--]);
}
Serial.println();
uint64_t c = a + b;
a = b;
b = c;
delay(100);
}
And then there is the big number class from Nick Gammon ....
you can add these lines to find (approx) the Golden Ratio
Serial.print('\t');
Serial.print((float)a/(float)b, 7);
converged quite fast
0 0.0000000
1 1 1.0000000
2 1 0.5000000
3 2 0.6666667
4 3 0.6000000
5 5 0.6250000
6 8 0.6153846
7 13 0.6190476
8 21 0.6176471
9 34 0.6181818
10 55 0.6179775
11 89 0.6180556
12 144 0.6180258
13 233 0.6180372
14 377 0.6180328
15 610 0.6180344
16 987 0.6180338
17 1597 0.6180341
18 2584 0.6180339
19 4181 0.6180340
20 6765 0.6180340
21 10946 0.6180340
22 17711 0.6180340
...
you can calculate nth Fibonacci directly with the golden ratio + 1 (PHI)
// FILE: fibonacci3.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.0.1
// PURPOSE: demo
// http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html
const double PHI = 1.61803398874989484820;
int cnt = 0;
void setup()
{
Serial.begin(115200);
Serial.println(__FILE__);
for (int i = 0; i < 92; i++)
{
Serial.print(i);
Serial.print('\t');
// Binet's Formula for the nth Fibonacci number
uint64_t a = round(pow(PHI, i) * (1.0 / sqrt(5)) );
// 64 BIT PRINT
char s[28];
int idx = 0;
uint64_t t = a;
while (t > 0)
{
s[idx++] = (t % 10) + '0';
t = t / 10;
}
idx--;
while (idx >= 0)
{
Serial.print(s[idx--]);
}
Serial.println();
delay(100);
}
}
void loop()
{
}
however it fails on the Arduino somewhere at 29th number
challenged by fibonaci I tried to find largest fibo number an Arduino UNO could generate and print.
It ended here with a 1778 digit nr. (Given 2K RAM that is not too bad)
// FILE: Fibonaci4.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.1.0
// PURPOSE: Generate Largest Fibonaci numbers possible with an UNO
// 880 ==> F8423 1760 digits
// 885 ==> F8471 1770 digits
// 886 ==> F8480
// 887 ==> F8490
// 888 ==> F8499
// 889 ==> F8509 1778 digits; even F8511 is also correct
// 890 ==> FAIL (probably stack meets heap)
#define NR 889
// every byte holds 2 digits 00..99, so up to 2xNR digits
uint8_t a[NR];
uint8_t b[NR];
void setup()
{
Serial.begin(115200);
memset(a, NR, 0);
memset(b, NR, 0);
b[0] = 1;
for (int x = 0; x <= 8515; x++) // <= NR * 10
{
if (x > 8500) // (un)comment this line to see them all
{
Serial.print(x);
Serial.print('\t');
for (int i = NR - 1; i >= 0; i--)
{
if (a[i] < 10) Serial.print(0);
Serial.print(a[i]);
}
Serial.println();
}
add();
}
}
void loop()
{}
void add()
{
for (int i = 0; i < NR; i++)
{
uint8_t t = a[i] + b[i];
a[i] = b[i];
b[i] = t;
}
// overflow correction,
// only for b[] if we do 2 loops
// merge loop with above loop and a[] needs to be corrected too
for (int i = 0; i < NR - 1; i++)
{
if (b[i] >= 100)
{
b[i] -= 100;
b[i + 1] += 1;
}
}
}
So the largest fibonaci number I could generate with an UNO was F8509.
F8510 and F8511 did overflow but were correctly printed.
8509 84400668190831278333126686020568946106614003082504815691896926120086131519066530270401365150210042570035634084935763826819099864112979376961661562417793900681836132737090783699187109752346894362146729443861932954797103558698690088556386363449839100798233428510045574404281650986095441352642766043355163610653801755941962458167776501827784067503772352220365476497251345399470656860558030204409880089039247426617320988738496392544021299822651623000444688282162592047232218746545194397654235083898448444745534967097958514311764995238775243162423291637586000207022796813218200598823807327545244893853216782407867479609892957746756822160315419219333173267392387825370120933834142318412505363382985472450967190350898502590685605876779301683036360354833085165222061655724331245008230894055479640998738672579350359616870897812480325092527549497779593983301658570788354314745461537933275154142846590337032275039396449662376080498360032118515390445213501565130538536367778461502545284853684869398312395906117279593258790138160015179339987928198402182503160808688764734348834481750099824697010799278937674376188007828065969973640859570189762195644772095085422354304121126909891490625344248410538967407128607033202635969935371117360366864194348298251565603036430286887699099574221488502532072212488664328217204094709791039588860704985604667942339738618630894438821813765433687821257650143695575216820605231112636773195666608116456908598045789161175106064241425067968307295582078012780293816412407165162239036229160909093238098333484300645840988885499648511476316906418259117725435323768154132836313652410150734466934385809642129791779055728697968868506140269519165712151562215621865405371741470824129239460211934080304413941783141547696833805271120951873987471301204306728566019963363270409
....
8511 220963817996798382910942772294426478096573113748757492444211706032603575028591589591830285820181857288071945503473881874755185832405608652208370453626383399498373507887413896700021031583605068993699743964022518831552203828441069209318004831457059988706854031043374552590129600055045646363813205304964329481126802679494093360645804279491652605011003831901896741617761752671547027624329981936920524476377116158769104548177899398782298078887817120245647193565893469631194914570055245914810246996267651056211573182808748490237920841748891626304104135517230402463120077711439851049323993973947710690752756803978290099416912586389146424532072048811768746420975498862552999402574098307714950819218036994630092546589976348370092002546007819888628846908652500941980926903888991682006584195372121784829683276479352411538689383612960646990184524429690119324797671646093961719666867656003489685665209101882844307101747721764553693812952073858069783545221835535173615054035257155793467934420974677612289049423661352961792301593082438708415564194769954765206466541396807998052334191754355823342020945469270470202632919037338484220322542625375882922427051697644991224086194358490554610430982412129342140226509949447597273676544951062705831602340721195389756916654472039385591541543850886536025299207383876172644619438002510141948329977963452472363655321302684635199172816446191451933714077890660824903056716986422613669658605709411760697783344526510071376831256243555309547600620480923020443550192801708401670414714824474072165043960875820848983400464618459578453377462052499028665974815088915198899357880162747105076981008710925856544810072426352731767850525487316189144739470633075448884498455974169432192372680233790740495494456074584572342652021829213816783887042631031915935993185842879714
Note: at 115Kbaud one can print ~10000 chars per second or ~5 fib numbers of this length.
printing all 8500 will take almost 30 minutes.
(and no they will not fit on an LCD anymore)
fun!
using an array of uint32_t I can squeeze 9 digits in 4 bytes instead of 8 in the code above.
using the same technique I now get a fibonacci number of 1999 digits with an UNO.
// FILE: Fibonacci5.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.1.0
// DATE: 2018-03-04
// PURPOSE: Generate Largest Fibonacci numbers possible with an UNO
// 222 ==> F9565 1999 digits;
// 223 ==> FAIL (stack meets heap)
#define NR 222
// every element holds 9 digits 0..999999999, so up to 9xNR digits
// except the last can hold 1 digit more .
uint32_t a[NR];
uint32_t b[NR];
void setup()
{
Serial.begin(115200);
b[0] = 1;
for (int x = 0; x <= 9600; x++) // x <= NR * 45
{
if (x > 9500) // (un)comment this line to see them all
{
Serial.print(x);
Serial.print('\t');
for (int i = NR - 1; i >= 0; i--)
{
if (a[i] < 100000000) Serial.print(0);
if (a[i] < 10000000) Serial.print(0);
if (a[i] < 1000000) Serial.print(0);
if (a[i] < 100000) Serial.print(0);
if (a[i] < 10000) Serial.print(0);
if (a[i] < 1000) Serial.print(0);
if (a[i] < 100) Serial.print(0);
if (a[i] < 10) Serial.print(0);
Serial.print(a[i]);
}
Serial.println();
}
add();
}
}
void loop()
{}
void add()
{
for (int i = 0; i < NR; i++)
{
uint32_t t = a[i] + b[i];
a[i] = b[i];
b[i] = t;
}
// overflow correction,
// only for b[] if we do 2 loops
// merge loop with above loop and a[] needs to be corrected too
for (int i = 0; i < NR - 1; i++)
{
if (b[i] >= 1000000000)
{
b[i] -= 1000000000;
b[i + 1] += 1;
}
}
}
To squeeze more I have to use uint64_t elements, but printing would be more complex.
64 bit could have 19 digits instead of 18 so max ~5% more ==> about 2100 digits should be possible
To me it looks like the printing is done without clearing the screen, leaving some leftover chars on the LCD when restarting at i=1.
Either print some blank chars after printing a, or clear the screen after the 'for' loop
(still off topic)
uint64_t version ==> F9820 -- 2052 digits.
// FILE: Fibonacci6.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.1.0
// DATE: 2018-03-04
// PURPOSE: Generate Largest Fibonaci numbers possible with an UNO
// 108 ==> F9820 2052 digits;
// 109 ==> FAIL (stack meets heap)
#define NR 108
// every element holds 19 digits
// except the last can hold 1 digit more .
uint64_t a[NR];
uint64_t b[NR];
void setup()
{
Serial.begin(230400);
b[0] = 1;
for (int x = 0; x <= 9825; x++) // x <= NR * 45
{
if (x > 9810) // (un)comment this line to see them all
{
Serial.print(x);
Serial.print('\t');
for (int i = NR - 1; i >= 0; i--)
{
if (a[i] < 1000000000000000000ULL) Serial.print(0);
if (a[i] < 100000000000000000ULL) Serial.print(0);
if (a[i] < 10000000000000000ULL) Serial.print(0);
if (a[i] < 1000000000000000ULL) Serial.print(0);
if (a[i] < 100000000000000ULL) Serial.print(0);
if (a[i] < 10000000000000ULL) Serial.print(0);
if (a[i] < 1000000000000ULL) Serial.print(0);
if (a[i] < 100000000000ULL) Serial.print(0);
if (a[i] < 10000000000ULL) Serial.print(0);
if (a[i] < 1000000000ULL) Serial.print(0);
if (a[i] < 100000000ULL) Serial.print(0);
if (a[i] < 10000000ULL) Serial.print(0);
if (a[i] < 1000000ULL) Serial.print(0);
if (a[i] < 100000ULL) Serial.print(0);
if (a[i] < 10000ULL) Serial.print(0);
if (a[i] < 1000ULL) Serial.print(0);
if (a[i] < 100ULL) Serial.print(0);
if (a[i] < 10ULL) Serial.print(0);
print64(a[i]);
}
Serial.println();
}
add();
}
}
void loop()
{}
void add()
{
uint64_t overflow = 0;
// max64_t 18446744073709551615
for (uint8_t i = 0; i < NR; i++)
{
uint64_t invert = 10000000000000000000ULL - a[i];
if (invert > b[i])
{
uint64_t t = a[i] + b[i];
a[i] = b[i];
b[i] = t;
if (overflow) b[i]++;
overflow = 0;
}
else
{
// overflow prevention,
uint64_t t = b[i] - invert;
a[i] = b[i];
b[i] = t;
if (overflow) b[i]++;
overflow = 1;
}
}
}
void print64(uint64_t t)
{
// 64 BIT PRINT
char s[24];
int idx = 0;
while (t > 0)
{
s[idx++] = (t % 10) + '0';
t = t / 10;
}
idx--;
while (idx >= 0)
{
Serial.print(s[idx--]);
}
}
(still off topic)
squeeeeeezed 19 extra digits -> F9911 == 2071 digits
I can see F10000 at the horizon...
// FILE: Fibonacci6.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.1.0
// DATE: 2018-03-04
// PURPOSE: Generate Largest Fibonaci numbers possible with an UNO
// URL: https://forum.arduino.cc/index.php?topic=532760.0
// 108 ==> F9820 2052 digits;
// 109 ==> F9911 2071 digits
// 110 ==> FAIL
#define NR 109
// every element holds 19 digits
// except the last can hold 1 digit more .
uint64_t a[NR];
uint64_t b[NR];
void setup()
{
Serial.begin(230400);
b[0] = 1;
for (int x = 0; x <= 9920; x++) // x <= NR * 45 10100
{
if (x > 9900) // (un)comment this line to see them all
{
Serial.print(x);
Serial.write('\t');
for (int8_t i = NR - 1; i >= 0; i--)
{
print64(a[i]);
}
Serial.write('\n');
}
add();
}
}
void loop()
{}
void add()
{
uint8_t overflow = 0;
// max64_t 18446744073709551615
for (uint8_t i = 0; i < NR; i++)
{
// detect overflow
uint64_t t = 10000000000000000000ULL - a[i];
if (t > b[i])
{
t = a[i] + b[i];
a[i] = b[i];
b[i] = t;
if (overflow) b[i]++;
overflow = 0;
}
else
{
// overflow prevention,
t = b[i] - t;
a[i] = b[i];
b[i] = t;
if (overflow) b[i]++;
overflow = 1;
}
}
}
void print64(uint64_t t)
{
// 64 BIT PRINT
char s[20];
int8_t idx = 0;
while (t > 0)
{
s[idx++] = (t % 10) + '0';
t = t / 10;
}
while (idx < 19) s[idx++] = '0'; // leading zeros
idx--;
while (idx >= 0)
{
Serial.write(s[idx--]);
}
}
update:
Found a bug in this code, the overflow is not handled correctly in some corner cases.
The algorithm fixes this in next iteration but some values are printed incorrect.
(version 5 is ok afaik)
Working on a fix - and a even more squeezed version.
(final fibonacci version for now)
Squeezed 63 digits more out of the UNO - F10209 - 2134 digit number
by using optimized packed array of 10 bit numbers (which caused slow code and other discomfort)
Verified numbers against python script,
// FILE: Fibonacci7.ino
// AUTHOR: Rob Tillaart
// VERSION: 0.1.2
// DATE: 2018-03-05
// PURPOSE: Generate large Fibonaci numbers with an uno
// URL: https://forum.arduino.cc/index.php?topic=532760.0
/*
Program uses compacte groups of 3 digits = 0..999
This fit in 10 bit giving a storage efficiency of 1000/1024 ~ 97%
(it has just enough spare to tackle overflow.
two arrays of 890 bytes can represent an 2136 digit number.
however packing and unpacking is slow.
@890 memory is minimal.
Global variables use 1964 bytes (95%) of dynamic memory,
leaving 84 bytes for local variables. Maximum is 2048 bytes.
==> F10209 - 2134 digit number
F0 .. F10209 matches the python fibonacci program below
a = 0
b = 1
for cnt in range(10250):
print cnt, a
(a,b) = (b, a+b)
cnt = cnt + 1
Could minimize the Serial buffers ...
*/
#define NR 712
#define ARSIZE (NR*10/8)
uint8_t a[ARSIZE];
uint8_t b[ARSIZE];
void setup()
{
Serial.begin(230400);
Serial.write('\n');
memset(a, ARSIZE, 0);
memset(b, ARSIZE, 0);
set(b, 0, 1);
for (int x = 0; x <= 1000; x++)
{
if (x < 1000 || x % 1000 == 0 || x >= 10200) // remove this to see them all
{
Serial.print(x);
Serial.write(' ');
bool skipMostLeadingZeros = true;
for (int16_t i = NR - 1; i >= 0; i--)
{
uint16_t t = get(a, i);
if (t == 0 && skipMostLeadingZeros) continue;
skipMostLeadingZeros = false;
if (t < 100) Serial.write('0');
if (t < 10) Serial.write('0');
Serial.print(t);
}
Serial.write('\n');
}
add();
}
}
void loop()
{}
// packs 4x3 digits in 5 bytes
uint16_t get(uint8_t *p, int idx)
{
uint16_t val = 0;
int b1 = (idx * 10) / 8;
int b2 = b1 + 1;
switch (idx % 4)
{
case 0:
val = p[b1];
val <<= 2;
val |= (p[b2] >> 6);
break;
case 1:
val = p[b1] & 0x3F;
val <<= 4;
val |= (p[b2] >> 4);
break;
case 2:
val = p[b1] & 0x0F ;
val <<= 6;
val |= (p[b2] >> 2);
break;
case 3:
val = p[b1] & 0x03;
val <<= 8;
val |= (p[b2]);
break;
}
return val;
}
void set(uint8_t *p, int idx, uint16_t val)
{
int b1 = (idx * 10) / 8;
int b2 = b1 + 1;
switch (idx % 4)
{
case 0:
p[b1] = val >> 2;
p[b2] = (p[b2] & 0x3F) | (uint8_t)(val << 6);
break;
case 1:
p[b1] = (p[b1] & 0xC0) | (uint8_t)(val >> 4);
p[b2] = (p[b2] & 0x0F) | (uint8_t)(val << 4);
break;
case 2:
p[b1] = (p[b1] & 0xF0) | (uint8_t)(val >> 6);
p[b2] = (p[b2] & 0x03) | (uint8_t)(val << 2);
break;
case 3:
p[b1] = (p[b1] & 0xFC) | (uint8_t)(val >> 8);
p[b2] = val & 0xFF;
break;
}
}
// add numbers in groups of 3 digits
void add()
{
// the grps indicates which elements of the array actually
// are > 0 so need to be added
// leading zeros do not need to be added.
static uint16_t grps = 2;
// overflow is tricky as compensating afterwards in a loop
// is not possible
uint8_t carry = 0;
for (uint16_t i = 0; i < grps; i++)
{
uint16_t ta = get(a, i);
uint16_t tb = get(b, i);
uint16_t tc = ta + tb + carry;
set(a, i, tb);
if (tc < 1000)
{
set(b, i, tc);
carry = 0;
}
else
{
tc -= 1000;
set(b, i, tc);
carry = 1; // add carry for next iteration
}
}
if (get(b, grps - 1) > 0) grps++;
}
// END OF FILE
updated add()