Hello, I am trying to get my Arduino to print the Fibonacci sequence but after it gets to the 22nd number (28657) it starts printing negative numbers. Does anyone else have this problem? if you know anything that would help it would be greatly appreciated.
Here is the code:
int num1 = 0;
int num2 = 1;
int num3;
void setup()
{
Serial.begin(9600);
}
void loop()
{
num3 = num1 + num2;
Serial.println (num3);
num1 = num2;
num2 = num3;
delay(200);
}
It's overflow. Variable type of int has range -32,768 to 32,767.
ahhhh, thank you vary much
You can go much higher (4.2 Billion) with 32-bit "unsigned long".
There is also a 64-bit "unsigned long long" that would get you 19 digits but Serial.print() can't handle that data type.
There is a BigNumber library: https://www.gammon.com.au/forum/?id=11519.
I took your sketch and changed it for BigNumber and put it in a Wokwi simulation:
Hit the start-button and it runs.
I don't know when the memory of the Arduino Uno is full, probably when the number is a few hundred digits long.
Wow, thank you very much for your help!
When I ran it, it stopped here:
29941786242203757034937742679847722285930070850760053628857379482552272854210034290353600980959455084033350473690872688601978897187669305042631491407198434363333507958485382908014045060473022993091179846948416491187003494754
I added a bit of code to show an iteration count and it stopped at the same place, iteration 1069.
The last answer is 224 digits long.
Wokwi can also simulate a Raspberry Pi Pico. After 22 minutes it did 37000 iterations and the number was 7734 digits long. Wokwi project: https://wokwi.com/arduino/projects/300138687195251210
The uint64_t on a Arduino Uno is more interesting. It turns out that it can only do 91 iterations. The sketch is below, and the Wokwi simulation is: https://wokwi.com/arduino/projects/300139385454592525
uint64_t num1 = 0;
uint64_t num2 = 1;
uint64_t num3;
int count = 0;
void setup()
{
Serial.begin( 115200);
Serial.println( "Fibonacci with 64-bit integers");
pinMode( 13, OUTPUT);
}
void loop()
{
num3 = num1 + num2;
num1 = num2;
num2 = num3;
Serial.print( count++);
Serial.print( ":");
println64( num3);
if( count >= 94)
{
Serial.println( "Stopped");
while(true)
{
digitalWrite( 13, digitalRead( 13) == HIGH ? LOW : HIGH);
delay( 200);
}
}
}
// print a unsigned 64 bit number as decimal
void println64( uint64_t u)
{
char buffer[25];
buffer[24] = '\0';
for( int i=23; i>=0; i--)
{
int d = (int) (u % 10);
buffer[i] = d + '0';
u /= 10;
}
Serial.println( buffer);
}
Since the calculation only involves adding two integers, and the hardest (and slowest) part will be the division needed to convert from binary to decimal for printing, I though I'd try doing it with binary coded decimal. Using two large arrays to hold the numbers, and overwriting the smallest number with the sum to avoid using a third array, I was able to get 8421 iterations on an UNO giving a 1760 digit number, and slightly over 37,000 iterations on a Mega. Surprisingly fast, a bit over six minutes on a Mega when printing every thousandth result.
//const size_t arraySize = 3868; //array to hold 7736 BCD digits on a mega, a bit over 37000 iterations
const size_t arraySize = 880; //array to hold 1760 BCD digits on an UNO, 8421 iterations
uint8_t num1[arraySize];
uint8_t num2[arraySize];
uint16_t loopcount = 0;
uint8_t* bcd1;
uint8_t* bcd2;
uint8_t* bcdTemp;
void setup() {
Serial.begin(115200);
//set num1 = 0, num2 = 1
for (size_t i = 0; i < sizeof(num1); i++) {
num1[i] = 0;
num2[i] = 0;
}
num2[sizeof(num2) - 1] = 1;
Serial.print(F("0:"));
printBCD(num2, arraySize);
bcd1 = num1;
bcd2 = num2;
}
void loop() {
addBCD(bcd1, bcd2, arraySize);
loopcount++;
if ((loopcount % 1000) == 0) {
Serial.print(loopcount);
Serial.print(':');
printBCD(bcd1, arraySize);
Serial.print(F("millis: "));
Serial.println(millis());
}
if ((bcd1[0] >> 4) > 4) { //stop when doubling the number would cause overflow
Serial.print(F("terminated at: "));
Serial.println(loopcount);
printBCD(bcd1, arraySize);
Serial.print(F("millis: "));
Serial.println(millis());
while (true) {};
}
//swap digits
bcdTemp = bcd1;
bcd1 = bcd2;
bcd2 = bcdTemp;
}
void addBCD(uint8_t* bcd1, uint8_t* bcd2, size_t bcd_size) {
//add bcd1 to bcd2, storing result in bcd1
uint8_t carry = 0;
uint8_t lowerBCD;
uint8_t upperBCD;
for (size_t i = 0; i < bcd_size; i++) {
size_t index = bcd_size - i - 1;
lowerBCD = (bcd1[index] & 0x0F) + (bcd2[index] & 0x0F) + carry;
if (lowerBCD > 9) {
lowerBCD = lowerBCD - 10;
carry = 1;
} else {
carry = 0;
}
upperBCD = (bcd1[index] >> 4) + (bcd2[index] >> 4) + carry;
if (upperBCD > 9) {
upperBCD = upperBCD - 10;
carry = 1;
} else {
carry = 0;
}
bcd1[index] = (upperBCD << 4) | lowerBCD;
}
}
void printBCD(uint8_t* bcd, size_t bcd_size) {
uint16_t numDigits = 0;
bool leadingZero = true;
for (size_t i = 0; i < bcd_size; i++) {
byte upperBCD = bcd[i] >> 4;
byte lowerBCD = bcd[i] & 0x0f;
if (leadingZero && !(upperBCD == 0)) {
leadingZero = false;
}
if (!leadingZero) {
Serial.write('0' + upperBCD);
numDigits++;
}
if (leadingZero && !(lowerBCD == 0)) {
leadingZero = false;
}
if (leadingZero && (i == bcd_size - 1)) {
leadingZero = false;
}
if (!leadingZero) {
Serial.write('0' + lowerBCD);
numDigits++;
}
}
Serial.print(F("\nnumber of digits: "));
Serial.println(numDigits);
}@david_2018 Your sketch on a Mega in Wokwi, it did not need any modifications: https://wokwi.com/arduino/projects/300172207599911434.
@coderturkey I hope you don't mind that we got a little carried away. I like the Wokwi simulator and I like the BigNumber library, so this was an interesting test.
This topic was automatically closed 120 days after the last reply. New replies are no longer allowed.