Hi everyone,
I'm trying to make a machine that calculates pi one digit at a time. I've already checked on the internet and I've found the bbp (Bailey-Borwein-Plouffe) formula which can do that but apparently only in hex and maybe binary.
I'm trying to figure out if there is a way to do the same thing using decimal numbers or either to convert the results of bbp algorithm in decimal i.e. converting hexadecimal pi to decimal pi.
Thank you for your help
discussed many times, I think last time was here
not an easy one with small SRAM
gamberoillecito:
Hi everyone,I'm trying to make a machine that calculates pi one digit at a time. I've already checked on the internet and I've found the bbp (Bailey-Borwein-Plouffe) formula which can do that but apparently only in hex and maybe binary.
I'm trying to figure out if there is a way to do the same thing using decimal numbers or either to convert the results of bbp algorithm in decimal i.e. converting hexadecimal pi to decimal pi.
The BBP algorithm is for calculation of "hex digits" of PI ONLY.
There is no possibility to calculate the Nth decimal place of PI in a similar way like it is with the Nth "hex digit".
There is a similar topic in this forum, started earlier this year in January, 2017:
https://forum.arduino.cc/index.php?topic=451743.0
In February I had put a lot of efforts in into programming some Arduino code for Bailey-Borwein-Plouffe algorithm running on Arduino UNO and posted the code in the other topic.
But it was a very frustrating experience: After posting the code for calculation of 4000 hex digits of PI, I got absolutely no comment or response from the starter of that thread.
But after I got no response from the starter of the topic for several weeks, I finally DELETED my code from the other topic, so it is GONE for now.
If you need decimal digits instead of hexdigits, it should be possible to create a decimal conversion algorithm.
BUT: You will first have to calculate a certain number of hex digits and store them intermediately, then have to convert them to decimal digits finally.
It should be doable for 1000 or 2000 decimal digits of PI on an UNO, I think (just a guess).
For number crunching of PI digits in decimal we need to have two things:
Are you ready?
As a first step I have some code for you, which can do none of the two steps:
The code just contains a pre-calculated list of some thousand hex digits of PI and displays the first 8366 of them on Serial.
In case anybody is interested in number crunching of PI digits with his Arduino, what would you like to
see next?
If anybody would be interested, I'd put some more efforts into it and post some more PI related stuff and Arduino code.
But in case nobody wants to see more, I'll just keep my ideas and code for myself.
you decide: Either reply something like "show me more PI related code" when interested.
Or reply something like "keep the PI calculation for yourself" when not interested.
Or just don't reply at all, if you don't want to see PI number crunching code.
It's up to you, again.
In the file attachment you find some code for just displaying a list of hex digits of PI, which is pre-calculated and stored in PROGMEM. Nothing is calculated at runtime in that code.
sketch_may22a.ino (29.2 KB)
I'd like to see some more about Pi code, in particular about how to decode hex digits to their decimal representation, thank you
IMHO if there is an algorithm to calculate Nth hex digit it must be possible to make one calculating Nth decimal digit. What is so special about hex vs. decimal related to pi?
I've had Pi memorized since college, 3.1415926535, kind of rolls off the tongue.
And for most things just using 3.14 has been enough.
Is it just an academic exercise to have more digits? Do they actually come in practical use for anything? Just curious. They're certainly not needed for digital circuit design.
Smajdalf:
IMHO if there is an algorithm to calculate Nth hex digit it must be possible to make one calculating Nth decimal digit. What is so special about hex vs. decimal related to pi?
well that's a good opinion now but has not been the ones from mathematicians: for centuries it was assumed that there was no way to compute the nth digit of PI without calculating all of the preceding n − 1 digits.
The Bailey–Borwein–Plouffe formula (BBP) for calculating PI was discovered in 1995 by Simon Plouffe. Using base 16 math, the formula can compute any particular digit of π—returning the hexadecimal value of the digit—without having to compute the intervening digits
--> read about the Bailey–Borwein–Plouffe formula and why HEX is good for this
In 1996, Simon Plouffe derived an algorithm to extract the nth decimal digit of PI (using base 10 math to extract a base 10 digit), and which can do so with an improved speed of O(n3log(n)3) time. The algorithm requires virtually no memory for the storage of an array or matrix so is indeed tediously achievable on a small micro controller.
CrossRoads:
Is it just an academic exercise to have more digits? Do they actually come in practical use for anything? Just curious.
well yes and know - depends the precision you want to achieve in calculations - but indeed it's more about the magic
The beauty of pi, in part, is that it puts infinity within reach. Even young children get this. The digits of pi never end and never show a pattern. They go on forever, seemingly at random—except that they can’t possibly be random, because they embody the order inherent in a perfect circle. This tension between order and randomness is one of the most tantalizing aspects of pi
Smajdalf:
IMHO if there is an algorithm to calculate Nth hex digit it must be possible to make one calculating Nth decimal digit.
Yes.
Smajdalf:
decimal digit. What is so special about hex vs. decimal related to pi?
The special thing with hex digits of PI is:
You can calculate each hex digit seperately, BEFORE calculating all the previous digits.
Let's say: You can calculate the 1000th hex digit of PI, without calculating the 999 leading hex digits first.
There is no similar algorithm for doing that in decimal:
In decimal you have to calculate the digits one after another: 1st digit first, 2nd digit second, and so on. And after you have calculated the 999th decimal digit, you then can calculate the 1000th decimal digit, not earlier.
This is completely different with hex digits:It sounds like a miracle, but with hex digits you can calculate the millionth hex digit initially, if you want. You don'tneed any digit before to calculate any other hex digit.
And of course you can do some brute-force algorithm to get the Nth decimal digit, like that:
Let's say, you want 1000 decimal digits:
First calculate the first 1000 hex digits and store them intermediately.
Then convert hex into decimal. You will get a little more decimal digits in the end: When having 1000 hex digits, you should be able to expand them to roughly 1150 decimal digits. Just do it, and if you need the 100th decimal digit, stop the conversion algorithm after you have expanded it.
jurs:
There is no similar algorithm for doing that in decimal:
this is not purely correct - read this research paper On the computation of the nth decimal digit of various transcendental numbers by Simon Plouffe
The method to calculate N digits of PI is centuries old. If you get through 2nd semester calculus you should learn finite series and be able to roll your own. Last time I did that kind of thing was maybe 1990 though so you'll have to look it up or find someone with a science degree and time.
Search: finite series calculate pi
You may also want to look into methods to compute with arbitrarily large numbers,
CrossRoads:
I've had Pi memorized since college, 3.1415926535, kind of rolls off the tongue.
And for most things just using 3.14 has been enough.Is it just an academic exercise to have more digits? Do they actually come in practical use for anything? Just curious. They're certainly not needed for digital circuit design.
I think, it's just for an academic exercise. Useful for nothing except showing-off.
Since electronic computers had been invented, all sorts of computers had been programmed to calculate many digits of PI accurately.
In 1949, the ENIAC - Wikipedia Computer held the world record in PI. That machine, which weighed many tons, could calculate 2037 digits of PI in 70 hours.
Chronology of computation of π - Wikipedia
So calculating more than 2037 digits of PI in less than 70 hours with an UNO and beat the 1949 world record of PI computation is just a programming exercise.
But I'm rather sure: Only very few forum members can actually do.
It's one thing to have a powerful microcontroller.
And it's another thing to develop powerful software for it.
Some can't.
And others just do it.
One interesting application would be to use it with distributed computing, so each computer could calculate a few digits. If it was an online app, people could contribute computer time and achieve a gradually, perpetually increasing precision value.
The series formula is available. More members can code that than can understand it. I can't really understand it any more for one, use it or lose it!
You learn the technique so you can apply it functions you don't have tables for or want more values than are available. It was a big day for me when I learned how to make the tables I had taken on faith in years before.
gamberoillecito:
I'd like to see some more about Pi code, in particular about how to decode hex digits to their decimal representation, thank you
Good news: I think I solved the problem of converting hex digits to decimal digits of PI.
And here is something I found out:
You need roughly 85 hex digits for expanding them into 100 decimal digits.
170 hex digits expand to 200 decimal digits.
850 hex digits are enough to expand 1000 decimal digits.
This has not really a mathematical background, and I am NOT a mathematician, I simply found out by experimenting with some code and comparing the results against PI-lists on the Internet.
Currently I'm working on an example program, which will contain about 2000 pre-calculated hex digits of PI in a PROGMEM array and provides a "Serial Command Menu" for the user, who can select either "hex digits mode" or "decimal digits mode" and whether he wants to see 100, 200, 300, 400, 500, 600, 700, 800 or 900 digits of PI in the serial monitor.As the hex digits are already included as a PROGMEM array, this will hardly need any processing time, just the time to send the digits to the serial monitor.
The code still needs some testing and brushing up, but hopefully I'm ready to post some Arduino PI related code by the end of the week, which can do at least a hex-digit-to-decimal-digit-expansion, while actually not calculating th the hex digits itself, but includes an array of pre-calculated hex digits.
Please stay tuned and come back to this topic, if your interest is on digits of PI.
Decimal is base 10, hex is base 16.
4 decimal digits: 0 to 9999, 4 places
4 hexadecimal digits: 0 to FFFF = 0 to 65535 still 4 places decimal since the 5th can't be > 6
6 decimal digits: 999999, 6 places
6 hexadecimal digits: 0 to FFFFFF = 16777216, 7 places decimal
8 decimal digits: 99999999, 8 places
8 hexadecimal digits: 0 to FFFFFFFF = 4294967296, 9 places decimal
16 hex digits is decimal 1.844674407×10¹⁹ ... 18 decimal digits
32 hex digits is decimal 3.402823669×10³⁸ ... 37 decimal digits
64 hex digits is decimal 1.157920892×10⁷⁷ ... 76 decimal digits
128 hex digits is decimal 1.340780793×10¹⁵⁴ ... 153 decimal digits
256 hex digits is decimal 1.797693135×10³⁰⁸ ... 307 decimal digits and doubling blows up my calculator.
Hex advances 16 to decimal's 10 per digit.
I lost my divide by 10 sketches that walked through multibyte integers nybble by nybble with carry. It worked regardless of word length and used lookup tables to run fast. There are faster divide-by-10 routines in archived Arduino furum threads and on The Playground as well but I dunno if they scale let alone to hideously large words. Funny but what you want from divide by 10 is the remainder.
Point is, conversion of binary values to decimal output is not a new topic in computing, there's tons of doc available. :o)
You could use BCD in byte arrays as 2-digit pairs. 'Only' 500 bytes for 1000 places and another 500 for scratch space.
Store and process the array to do your calculations in decimal using the same techniques you would with pencil and paper, do they teach that any more?
BCD is Binary Coded Decimal where 8 bits holds 2 4-bit decimal values, 0 to 9. You only need to operate on single digits in pencil and paper land for plus, minus, etc. You chain along the digits, the number length can be arbitrary. And... getting the output in decimal won't be a problem even with 1000 places or more. You can pick a place and get the digit, get sequences of digits.... I guess it does have practical applications!
GoForSmoke:
16 hex digits is decimal 1.844674407×10¹⁹ ... 18 decimal digits
32 hex digits is decimal 3.402823669×10³⁸ ... 37 decimal digits
64 hex digits is decimal 1.157920892×10⁷⁷ ... 76 decimal digits
128 hex digits is decimal 1.340780793×10¹⁵⁴ ... 153 decimal digits
256 hex digits is decimal 1.797693135×10³⁰⁸ ... 307 decimal digits and doubling blows up my calculator.
Very good explanation - WELL DONE!
So indeed, you can expand any given number of hex digits to some more decimal digits. Or the other way round: If you want to get a certain number of decimal digits, you need some less hex digits to encode them.
The same math which works for the whole integer part of hex and decimal numbers, will also work for the fractions part of a number.
How much is the difference?
I'd like to introduce the "hexFactor" for that:
float hexFactor=log(10)/log(16);
= 0.830482
Let's assume you want 100 decimal digits of PI, then dmultiply the number of decimal numbers you want by the hexFactor and round up to the next number:
100*0.830482= 83.0482, rounded up=84
So calculating 84 hex digits of PI should be enough for getting 100 decimal digits finally,after doing the hex-to-decimal expansion.
Or you want 1000 decimal digits of PI:
1000*0.830482=0830.482 rounded up=831
So you have to calculate 831 hex digits of PI, if you actually want to show 1000 decimal digits of PI.
OK so far?
I hope so.
And now I'm going to do some C code for expanding hex digits to decimal digits.
Seems to be hard to find existing code on the Internet for AVR GCC to expand huge amounts of hex digit fractions into even more decimal digit fractions.
1000 BCD digits takes 500 bytes as opposed to 416 bytes binary. Not a great savings with binary. I'd go with BCD as simpler, no need to convert the value to decimal. It would be slower except for the output conversion, there it would rock.
My first "personal computer" was a 4-bit machine, a TI SR-56.
GoForSmoke:
1000 BCD digits takes 500 bytes as opposed to 416 bytes binary. Not a great savings with binary. I'd go with BCD as simpler, no need to convert the value to decimal. It would be slower except for the output conversion, there it would rock.
So essentially you are telling, that the full amount of hex digits can be stored in half the number of bytes: One nibble per hex-digit instead of one byte per hex-digit.
Example: The first 64 hex digits of PI are:
243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89
and it is possible to store those 64 hex digits in just 32 bytes like that:
uint8_t hexDigits[] =
{
0x24, 0x3F, 0x6A, 0x88, 0x85, 0xA3, 0x08, 0xD3,
0x13, 0x19, 0x8A, 0x2E, 0x03, 0x70, 0x73, 0x44,
0xA4, 0x09, 0x38, 0x22, 0x29, 0x9F, 0x31, 0xD0,
0x08, 0x2E, 0xFA, 0x98, 0xEC, 0x4E, 0x6C, 0x89,
};
While this helps a lot to save intermediate (RAM) storage area for storing hex digits before decimal conversion,
this does not help me at all to develop an algorithm for decimal conversion of hex digits into decimal.
But I'm working on it.
gamberoillecito:
I'd like to see some more about Pi code, in particular about how to decode hex digits to their decimal representation, thank you
I'm currently working a lot on "how to decode hex digits to their decimal representation".
And I think, that I'm on a good way to solve it.
Maybe by next weekend, I can possibly show some demonstration code, which does the trick.
Stay tuned an come back to this topic in a couple of days!