Great day everyone,
I wanted to make a little PI gadget for a while. It would sit somewhere for a year or more and just calculate PI. Easy enough, isnt it? Not really, at least I havent been able to do it yet. Ive been using the Gregory-Leibnitz method for calculating pi to couple of decimal places but that requies constantly growing numbers -> variables will overflow eventually. Does anyone know of a method that wouldnt be variable size dependant?
Thanks
try pi: x * sin(180 / x)
x is the biggest number you can get like an unsigned long.
The bigger the closer to pi.
what would overflow - the denominator? sure after a while
Gregory-Leibnitz
PI = (4/1) - (4/3) + (4/5) - (4/7) + (4/9) - (4/11) + (4/13) - (4/15) ...
You real challenge is more in the precision of the floating point calculation...
you will need to implement yourself large precision maths otherwise your digits will end up wrong
PS: Nilakantha converges faster
PI = 3 + 4/(234) - 4/(456) + 4/(678 ) - 4/(8910) + 4/(101112) - 4/(121314) ...
Use Nick Gammon's implementation of the big number library.
There, he shows how to calculate e to an arbitrary number of places.
Wojta:
Great day everyone,
I wanted to make a little PI gadget for a while. It would sit somewhere for a year or more and just calculate PI. Easy enough, isnt it? Not really, at least I havent been able to do it yet. Ive been using the Gregory-Leibnitz method for calculating pi to couple of decimal places but that requies constantly growing numbers -> variables will overflow eventually. Does anyone know of a method that wouldnt be variable size dependant?
Thanks
Try Monte Carlo simulation... There are some stuff in Python!
There are methods that specifically calculate the nth digit of pi. These would allow you to spit out digits one by one without needing to compute the whole thing.
From what I have read, to convert any one hexadecimal digit for pi to one of the decimal digits requires having knowledge of all the hex digits that precede it. In any case, the Nth hex digit would not correspond to the Nth decimal digit.
So you would still need arbitrary precision arithmetic. Or, be happy knowing the Nth hex digit!
You could use Nick's port of bc to do big number calculation
Remember limited ram on an arduino means you won't be able to remembers tons of digits anyway which might become your limiting factor rather than raw power
In my believe it should be enough to use uint8_t variables for decimal digits and hex digits
I believe that is the way the BigNumber code works.
What if you used an SD card instead of RAM?
PaulMurrayCbr:
There are methods that specifically calculate the nth digit of pi. These would allow you to spit out digits one by one without needing to compute the whole thing.
The nth binary digit.
Just saying'
[EDIT: never mind.]
alto777
Wojta:
Great day everyone,
I wanted to make a little PI gadget for a while. It would sit somewhere for a year or more and just calculate PI. Easy enough, isnt it? Not really, at least I havent been able to do it yet. Ive been using the Gregory-Leibnitz method for calculating pi to couple of decimal places but that requies constantly growing numbers -> variables will overflow eventually. Does anyone know of a method that wouldnt be variable size dependant?
Is this topic dead already, with no final solution offered?
last month I suggested, implementing the Bailey-Borwein-Plouffe algorithm in Arduino, which is able to calculate "hex digits" of PI up to an arbitrary number of places. The algorithm does not throw out "decimal digits" of PI, but some kind of weird "hex digits" of PI, which need some post-processing: After a certain number of hex digits have been calculated and put into some intermediate storage area, maybe some bytes of RAM or maybe EEPROM or maybe SD card, you then can do a decimal expansion and expand hex digits into decimal digits and finally get PI accurate to a huge amount of decimal digits to print them on screen, serial monitor or where you want them to appear.
And more than that: While the Bailey-Borwein-Plouffe algorithm is using 64-bit "double" precision math, normally, I managed to create a code for the Atmega based Arduino boards, which uses "int" and "float" in single precision only for calculating 4000 hex digits of PI. The Internet helped me a lot to do so. Finally I posted the full code for Arduino UNO in this topic, it was in reply#11
Unfortunately, nobody seemed to be interested: Nobody tested my code and nobody ent a few words of comment as a reply, despite my offer, that I would do some more work on the code and extend the code to also do the "hex-digit-to-decimal-digit-expansion finally.
As I got absolutely no feedback, I deleted all my earlier replies in this topic, in cluding the former "reply #11", which contained the full version of a "4000-hex-digits-calculation-of-number-PI" for Arduino UNO, posted along with the offer to do some more workd on the algorithm to also create decimal digits of PI, not only hex digits as it was.
I got absolutely no feedback, so now its gone: I DELETED ALL FROM THIS TOPIC.
It looks as if I had over-estimated the interest of the forum users, including interest of the topic-starter, in number crunching of many digits of PI.
It is as it is.
Coding costed my of couple of days of my life.
But nobody seems to be interested in the code.
So I say "GOOD BYE" to this topic.
GOOD BYE
jurs:
I got absolutely no feedback, so now its gone: I DELETED ALL FROM THIS TOPIC.It looks as if I had over-estimated the interest of the forum users, including interest of the topic-starter, in number crunching of many digits of PI.
It is as it is.
Coding costed my of couple of days of my life.
But nobody seems to be interested in the code.
So I say "GOOD BYE" to this topic.GOOD BYE
Very sorry this happened... I would be very interested since I am looking for ways to calculate pi with Arduino UNO these days...
1 Like
jurs:
I got absolutely no feedback, so now its gone: I DELETED ALL FROM THIS TOPIC.
It looks as if I had over-estimated the interest of the forum users, including interest of the topic-starter, in number crunching of many digits of PI.
:o :o :o :o :o :o :o :o :o :o :o :o :o :o :o :o :o :o :o
excuse my french but why on earth would you remove information you took time to post? that could have been useful to someone months ahead?
that could have been intellectually interesting to read, even when we don't participate....
what's your motivation? not enough karma?
just don't get it...
EDIT: did not see that this thread was actually very old...
1 Like
jurs:
Yes, that would be no problem, I think. The Bailey-Plouffe algorithm is not bound to store the hex digits in a certain type of memory. The only thing with this algorithm is: You first have to calculate a certain amount of hex digits, before you can start expanding them to decimal digits of PI. So calculating an arbitrary number of decimal digits of PI is always a 2-pass cycle:
1st pass: calculate a certain amount of hex digits and store them (whereever you want)
2nd pass: expand the previously calculated hex digits to decimal digits.I think the decimal expansion expands about two decimal digits from one hex digit.
So I think an UNO can calculate possibly up to 2000 decimal digits of PI, just using SRAM memory:
- calculate first 1000 hex digits of PI, store them in a byte-array of 1000 bytes
- then expand to 2000 decimal digits of PI
With using SD card this can be extended to about 5000 decimal digits of PI, calculated from an UNO:
- calculate 2500 hex digits and store them in a file on SD card.
- then expand those 2500 hex digits into 5000 decimal digits of PI
Runtime should be "several hours, hardware needed "UNO and SD card moduleA MEGA2560 has much more RAM than an UNO and can do all calculations and data storing within RAM for 5000 decimal digits of PI, I think, whithout any need of SD card for 5000 decimal digits of PI.
An UNO can possibly calculate up to 2000 or maybe 3000 decimal digits of PI, just using the SRAM in the Atmega328.
Maybe 5000 digits at most when using both, SRAM and EEPROM memory for storing intermediate hex digit values before finally expanding to decimal digits.@Wojta: What do you expect? How many digits of PI do you want to calculate? The Bailey-Plouffe algorithm as I have implemented it in my code (not yet fully finished) should be good for 5000 digits on an UNO at most, and the calculations of 5000 digits will take approximately "several hours to finish with 5000 digits of PI. Currently I have no algorithm to provide more digits in more time on an UNO. Please let me know if I shall finish the code for 2000, 3000 or 5000 digits of PI finally and post a copy of it.
TBTW: It's finished!
I could manage to add "decimal digit expansion" to the code I already posted in reply#11 and now I'm testing alittle bit what an UNO can do in calculating PI.These are my testing results:
- 50 digits of PI in less than one second
100 digits of PI in less than three seconds
500 digits of PI in less than one minute
1000 digits of PI in less than five minutes
2000 digits of PI: in less than 20 minutes, but last two digits seem to be wrong
[Edit] Oh, sorry, nothing wrong with 2000 digits of PI. Unfortunately I had done the initial comparison with a page listing, where each line was formatted to 77 digits while I programmed a sketch for my UNO which prints exactly 50 decimal digits of PI per line.So: All 2000 digits of PI are fully correct, when calculated using an UNO and comparing the result against lists of PI digits which can be found on the Internet.
1 Like
jurs:
OK, I played a little bit around with the code I posted in reply #11 yesterday, and within a couple of hours of UNO runtime I found out:My code can create the first 4038 hex digits of PI correctly within some hours, just using data types uint8_t, uint16_t and float, sending them to the serial monitor. For more hex digits the algorithm for Arduino UNO goes haywire,
[Edit/Correction]: Meanwhile I could manage to find a code on the Internet, which is a lttle bit better:
This code had been posted five years ago in a German microcontroller forum, it is for AVR GCC compiler and can calculate hex digits correctly up to 4100 hex digits:
pi.c - Mikrocontroller.net4100 correct hex digits is not a big improvement against 4038 correct hex digits, it is just pushing the limits a little bit.
But either number of hex digits (4038 or 4100) should be good enough to expand them to 5000 decimal digits of PI.
Unfortunately some storage area is needed temporarily to store hex digits before they can be expanded into decimal digits.
This will limit the number of decimal digits of PI on an UNO to maybe 3000, whithout using extra storage, i.e. "SD card" for storing hex digits temporarily before expanding them to decimal digits.
If somebody would be interested in code for calculating PI up to 1000, 2000 or even 3000 decimal digits on an UNO,, I'd give it a try to create some all-in-one code for both tasks:
- calculating hex digits and store them
- expanding hex digits of PI to decimal digits of PI.
The RAM of an UNO should be sufficient for calculating at least 3000 decimal digits of PI on an Atmega328 in internal 2KB SRAM only, no SD card needed.If nobody is interested, I'll do the code for myself and put it away.
jurs:
And this is the Bailey-Borwein-Plouffe algorithm for calculating "hex digits of PI" in Arduino:// Bailey-Borwein-Plouffe PI algorithm by 'jurs' for Arduino forum:
#define cput(x) Serial.write(x);
#define DIGITS 100
void setup()
{
Serial.begin(9600);
unsigned long time=millis();
Serial.print("\nCalculate first ");
Serial.print(DIGITS);
Serial.println("\thex digits of PI");
hexDigits();
Serial.print("Calculation time in seconds:\t");
Serial.println((millis()-time)/1000.0);
}
void loop() {
// put your main code here, to run repeatedly:
}
static uint8_t hexdigit (uint8_t n)
{
n += '0';
return n > '9' ? n + 'A'-'0'-10 : n;
}
static unsigned mod_mul (unsigned a, unsigned b, unsigned n)
{
unsigned ab = 0;
while (1)
{
if (a % 2 == 1)
{
ab += b;
if (ab >= n)
ab -= n;
}
a = a / 2;
if (a == 0)
return ab;
b = b * 2;
if (b >= n)
b -= n;
}
}
// Return 16^k mod n
//
// Exponentiation with the same approach as above except
// that we binary-expand the exponent instead of a factor.
static unsigned mod_pow16 (unsigned k, unsigned n)
{
unsigned p = 1;
unsigned _16 = 16;
if (n == 1)
return 0;
while (_16 >= n)
_16 -= n;
while (1)
{
if (k % 2 == 1)
p = mod_mul (_16, p, n);
k = k / 2;
if (k == 0)
break;
_16 = mod_mul (_16, _16, n);
}
return p;
}
// Helper for the function below.
static float tame (float s)
{
int8_t si = (int8_t) lrintf (s);
if (si <= -2 || si >= 2)
s -= si;
return s;
}
// The finite part mod 1 of sigma_j, i.e. partial sum where the exponent
// of 16 is >= 0. By "mod 1" we always mean "up to some integer",
// i.e. the result needs not to be normalized to [0,1).
static float sigma_a (unsigned n, uint8_t j)
{
float s = 0.0f;
for (unsigned k = n-1; k+1 != 0; k--)
{
unsigned j_8k = j + 8*k;
s += mod_pow16 (n-k, j_8k) / (float) j_8k;
// Cut down the sum and don't let it grow too big.
// The bigger the number grows the less precision is
// left for the fractional part we are interested in.
s = tame (s);
}
return s;
}
#define MARGIN 10
static float sigma_b (unsigned n, uint8_t j)
{
float s = 0;
float _16 = 1.0f;
for (unsigned k = n; k <= n + MARGIN; k++)
{
s += _16 / (8*k + j);
_16 /= 16;
}
return s;
}
// Compute an approximation of 16^n * sigma(j) mod 1
// where
//
// sigma_j = \sum_0^oo 1 / (16^k * (8k + j))
//
// The sum is split into two parts:
// sigma_a is the finite sum up to n.
// sigma_b is the finite sum from n+1 to oo
// and approximated by a sum from n+1 to n+MARGIN
float sigma (unsigned n, uint8_t j)
{
return sigma_a (n, j) + sigma_b (n, j);
}
// Compute pi * 16^n up to some integer
// using a Bailey-Borwein-Plouffe formula for pi:
//
// pi = 4sigma_1 - 2sigma_4 - sigma_5 - sigma_6
//
// with the definition of sigma_j from above. All this
// is explained very nicely in the French wikipedia at
// Formule BBP — Wikipédia
//
// For a proof define the power series
//
// sigma_j (x) = \sum x^{8k} / (8k + j)
//
// write the sum as integral and evaluate it at
// x = sqrt(1/2), see The world of Pi - Simon Plouffe / David Bailey
float pi_n (unsigned n)
{
float s = 0.0;
for (uint8_t i = 0; i < 4; i++)
{
// j[i] = 1, 4, 5, 6
uint8_t j = i ? i + 3 : 1;
// c[i] = 4, -2, -1, -1
int8_t c = -1;
if (i == 0) c = 4;
if (i == 1) c = -2;
s += c * sigma (n, j);
}
return s;
}
// We computed pi_n = 16^n * pi mod 1
// Get the first fractional hexadecimal digit by multiplying
// with 16 and extracting digit 0 of the result. Voila!
static uint8_t pi_dig16 (unsigned n)
{
return 15 & lrintf (floorf (16 * pi_n (n)));
}
void hexDigits()
{
// As explained above, 16-bit integers limitate us to moduli <= 2^15.
// The biggest modulus for n is 8n+6 so that for n >= 4096 we expect
// garbage from the implementation if 16-bit integers are used like
// with avr-gcc. In fact, we get garbage for n > 4100.
// It's not exacly 4095 because of the denominators in sigma_a that
// delay the garbage for some values of n.
// Easy going 4000 hex-digits of pi.
for (unsigned n = 0; n < DIGITS; n++)
{
// Print a line break after every 64 digits. That way the output
// can easily be compared with, e.g. the hexadecimal representation
// of pi from blowfish listed in "First 8366 Hex Digits of PI" from
// Cryptography Tutorials - Herong's Tutorial Examples
if (n % 64 == 0)
cput ('\n');
// Get the n+1-th hexadecimal digit of pi and
// output it as ASCII character.
cput (hexdigit (pi_dig16 (n)));
}
cput ('\n');
}
The number of hex digits to calculate is in a #define statement and can be changed easily. I have formatted output to print 64 hex digits per line, so it is easy to check correctness against tables which are available on the Internet like http://www.herongyang.com/Cryptography/Blowfish-First-8366-Hex-Digits-of-PI.html So, the first part in coding has been finished. Is there anybody out there and wants to see decimal digits of PI instead of hex digits? Maybe I could put some extra efforts into the code and do the second part: Decimal expansion of hex digits. I don't know how much work this might be and how it is to be done exactly. But I would give it a try if somebody is interested. BTW: My testing result is, that the calculation of the first 100 hex digits of PI takes 2.34 seconds. Not so bad. Or what do you think?
1 Like
jurs:
Yes, I think you are right as far as you are saying that you have to calculate N "hex digits" if you actually want to have N "decimal digits"of PI. That's the same I found out with my Plouffe algorithm experiments in Arduino code a while ago.But I think you are wrong about the need of arbitrary precision arithmetic. In my believe it should be enough to use uint8_t variables for decimal digits and hex digits, and no more than uint16_t and float types are necessary for the calculations. At least for N=1000 (or maybe even some more) decimal digits of PI.
jurs:
Dear Arduino programmers and PI calculation hobbyists!Has anybody written an algorithm for ]the miraculous Bailey-Borwein-Plouffe Pi algorithm and Arduino yet?
Just to find out, how many decimal digits of PI can be calculated using an UNO in a reasonable time of let's say "two minutes"?
I think two or three years ago I did some starting with Arduino coding for Bailey-Borwein-Plouffe method of calculating PI.
Unfortunately the Bailey-Borwein-Plouffe Pi Algorithm does NOT calculate decimal digits of PI, but something very weird the authors have given the name "hex digits". Not an easy task to convert those weird "hex digits" into normal decimal digits of PI. But it can be done.Would anybody still be interested in finding out how many decimal digits of number PI can be calculated using an Arduino UNO (Atmega328)?
If so, I could give it a try and look up my older source codes to find some suitable code for calculating an arbitrary number of digits of PI in reasonable time.In case you are interested, please leave a short reply to this message and I'll do my best to find some old code I wrote for the Bailey-Borwein-Plouffe Pi algorithm on Atmega controllers like UNO.What do you think? Can an UNO calculate PI up to one hundred or possibly up to one thousand decimal digits following the decimal point in a reasonable amount of time?
BTW: I forgot to mention: It requires much more efforts to write an algorithm and make an UNO calculate many digits of PI than to find many digits of PI on the Internet using Google:
http://www-groups.dcs.st-and.ac.uk/history/HistTopics/1000_places.html
Sorry for the inverted chronology
Dr. AWOL just grabbed the defibrillator - lol