1 | // Arduino demo sketch calculating Fibonacci numbers
|
2 | // by 'jurs' for Mikrocontroller.net forum
|
3 | // tested with Arduino UNO (Atmega328, 2KB RAM) and Arduino v1.0.5
|
4 |
|
5 | // internal data type (byte array) to represent "very big" numbers
|
6 | // use a size of 855 or less for Arduino UNO with 2KB RAM
|
7 | // each byte of the array represents two digits of a very big number (00...99)
|
8 | typedef byte bignum_t[855]; // max. size depends on available RAM
|
9 |
|
10 | int bigDigits(byte* num)
|
11 | // count digits and return "length" of the number representation
|
12 | {
|
13 | boolean leadingZero=true;
|
14 | int result=0;
|
15 | for (int i=0;i<sizeof(bignum_t);i++)
|
16 | {
|
17 | if (leadingZero)
|
18 | {
|
19 | if (num[i]!=0)
|
20 | {
|
21 | leadingZero=false;
|
22 | if (num[i]>=10) result++;
|
23 | result++;
|
24 | }
|
25 | }
|
26 | else
|
27 | {
|
28 | result+=2;
|
29 | }
|
30 | }
|
31 | return result;
|
32 | }
|
33 |
|
34 |
|
35 | void bigAssign(byte* dest, byte num)
|
36 | // very limited function to assign a number to the "very big number array"
|
37 | // can only assign initial numbers up to 99
|
38 | {
|
39 | memset(dest,0,sizeof(bignum_t));
|
40 | if (num<=99) dest[sizeof(bignum_t)-1]=num;
|
41 | }
|
42 |
|
43 | boolean bigAdd(byte* n1, byte* n2)
|
44 | {
|
45 | // adds two very big numbers.
|
46 | // n2 is added to n1, so the final result is returned in n1
|
47 | // returns error value if overflow occurs
|
48 | int temp=0; // carry value
|
49 | for (int i=sizeof(bignum_t)-1;i>=0;i--)
|
50 | {
|
51 | temp=temp+n1[i]+n2[i];
|
52 | if (temp<100) // no carry
|
53 | {
|
54 | n1[i]=temp;
|
55 | temp=0;
|
56 | }
|
57 | else // carry
|
58 | {
|
59 | n1[i]=temp-100;
|
60 | temp=1;
|
61 | }
|
62 | }
|
63 | return temp;
|
64 | }
|
65 |
|
66 | void bigPrint(byte* num)
|
67 | // send output of a very big number to Serial
|
68 | {
|
69 | boolean leadingZero=true;
|
70 | for (int i=0;i<sizeof(bignum_t);i++)
|
71 | {
|
72 | if (leadingZero)
|
73 | {
|
74 | if (num[i]!=0)
|
75 | {
|
76 | leadingZero=false;
|
77 | if (num[i]>=10) Serial.print(num[i]/10);
|
78 | Serial.print(num[i]%10);
|
79 | }
|
80 | }
|
81 | else
|
82 | {
|
83 | Serial.print(num[i]/10);
|
84 | Serial.print(num[i]%10);
|
85 | }
|
86 | }
|
87 | }
|
88 |
|
89 |
|
90 | void printFiboResult(int num, byte* fib)
|
91 | // send output of a calculated Fibonacci number to Serial
|
92 | // Function sends the index count and Fibonacci number in one line
|
93 | // and the number of digits of the calculated number in the next line
|
94 | {
|
95 | Serial.print(num); // index
|
96 | Serial.print('\t');
|
97 | bigPrint(fib); // Fibonacci number
|
98 | Serial.println();
|
99 | Serial.println(bigDigits(fib)); // number of digits
|
100 | }
|
101 |
|
102 | void setup()
|
103 | {
|
104 | Serial.begin(115200);
|
105 | Serial.println(F("i\tFibonacci(i)"));
|
106 | unsigned long time=millis();
|
107 | bignum_t fibNum1; // Declare two "very big number" arrays
|
108 | bignum_t fibNum2;
|
109 | byte* pfibNow=fibNum1; // Pointer to the value of the (i)th fibonacci number
|
110 | byte* pfibNext=fibNum2; // Pointer to the value of the (i+1)th fibonacci number
|
111 | int i=1,error;
|
112 |
|
113 | bigAssign(pfibNow,1); // Assign initial value to first Fibonacci number
|
114 | printFiboResult(i,pfibNow); // print it
|
115 | bigAssign(pfibNext,1); // Assign initial value to next Fibonacci number
|
116 | while(1)
|
117 | {
|
118 | i++;
|
119 |
|
120 | if (i<20 || i%64==0) // do some output on Serial in some cases
|
121 | {
|
122 | printFiboResult(i,pfibNow);
|
123 | }
|
124 |
|
125 | error=bigAdd(pfibNext,pfibNow); // add the two very big numbers
|
126 | if (error) break;
|
127 | byte* temp=pfibNow; // now change the number pointers with each other
|
128 | pfibNow=pfibNext;
|
129 | pfibNext=temp;
|
130 | }
|
131 | time=millis()-time;
|
132 | Serial.println(F("Letzte berechnete Zahl:"));
|
133 | printFiboResult(i,pfibNow);
|
134 | Serial.print(F("Berechnet in "));
|
135 | Serial.print(time/1000.0,3);
|
136 | Serial.println(F(" Sekunden"));
|
137 | }
|
138 |
|
139 |
|
140 | void loop()
|
141 | {
|
142 | }
|