-- More e digits trivia. -- Feel free to copy, distribute as long as this header attached so -- original algorithm creators and implementors are known. -- -- This is an Ada implementation of decimal representation of 'e' -- based on SPIGOT algorithm for \pi by -- S. Rabinowitz & S. Wagon, _The_American_Mathematical_Monthly_, March 1995 -- -- A C implementation of the above was posted on the net by -- Ed Hook -- MRJ Technology Solutions, Inc. -- NAS, NASA Ames Research Center -- Internet: hook@nas.nasa.gov -- -- This is an Ada implementation of the above using GNAT (gnu Ada compiler), -- with the added feature is that it computes the frequency of each digit in e, -- and computes the largest consecutive sequences of each digit within the -- expression that represents digits of e. -- -- the following is the result. my PC is still running trying to find the -- frequency for 200,000 digits and more for e, and it's been several days -- and not finished. So this is a partial results. (PC is 200 MHz pentium, -- running Linux 2.0.36, and compiler is GNAT 3.11p -- -- offcourse as number of digits of e goes very large, each digit is expected -- to show as often as any other digit. -- -- Nasser Abbasi nabbasi@pacbell.net feb. 20, 1999. -- -- results: -- this is distribution table for digits in e as function of how many -- digits. -- for example, when looking at 5000 digits of e, we find 497 0's, -- 478 1's, etc.. (this is for digits after the decimal point of e) -- -- -- #digits in e -- -------------------------------------------------------------- -- 500 5,000 20,000 50,000 200,000 -- --------------------------------------------------------------- --how many 0's 51 497 1,949 4,948 19,916 --how many 1's 43 478 2,010 5,055 20,367 --how many 2's 50 492 2,020 4,969 19,794 --how many 3's 53 514 2,080 5,026 20,071 --how many 4's 52 470 1,989 4,966 20,082 --how many 5's 44 478 1,979 5,046 20,038 --how many 6's 51 545 2,057 5,133 20,221 --how many 7's 60 525 1,977 4,959 19,817 --how many 8's 40 509 1,966 4,972 19,939 --how many 9's 56 492 1,974 4,926 19,755 -- ------------------------------------------------------------------------ --most occurring '7' '7' '3' '6' '1' ------------------------------------------------------------------------ --least occurring '8' '4' '0' '9' '9' ------------------------------------------------------------------------ --difference --between largest 20 55 131 207 612 --and smallest --in frequency ------------------------------------------------------------------------ --difference --between largest 4% 1.1% 0.655% 0.414% 0.306% --and smallest --frequency in % -- -- --consecutive frequencies: under each column, there are 3 values, the first --is the number of digits that occurred next to each others for that digit, --and the start of this sub sequence, and its end, in position values. -- --for example, for 5,000 digits of e, we see that largest consecutive --sequence of digit '0' had length of 3, and it started at digit position --328 to position 330. Digit positions are counted from left to right at --the decimal point. for example e=2.718, here digit '7' is at position 1, --'1' is at position 2, etc.. -- -- #digits in e -- ----------------+-----------------+----------------------------------- -- 5,000 | 20,000 | 50,000 | 100,000 -- ----------------+------------------+------------------+--------------- -- 0's (3,328,330) | (4,7688,7691) | *no change* |(6,89296,89301) -- 1's (3,427,429) | (5,12220,12224) | *no change* | *no change* -- 2's (2,2744,2746) | (4,17309,17312) | (5,33483,33487) | *no change* -- 3's (4,3354,3375) | *no change* | *no change* | *no change* -- 4's (3,787,789) | (4,11806,11809) | *no change* | *no change* -- 5's (4,3620,3623) | *no change* | *no change* | *no change* -- 6's (5,4992,4996) | *no change* | *no change* | *no change* -- 7's (4,1071,1074) | *no change* | *no change* | *no change* -- 8's (4,723,726) | *no change* | *no change* | *no change* -- 9's (3,47,49) | *no change* | (4,29344,29347) | *no change* -- -- -- --Compiler: GNAT 3.11p , see http://www.adahome.com to download --To compile: save this file as dist_e_final.adb and type -- gnatmake dist_e_final.adb --system: Linux 2.0.36 --Date: feb. 17, 1999 --To Run: ./dist_e_final -- For example, to see e for 70 digits do: -- -- /home/nabbasi/my_ada $./dist_e_final 70 -- 2.7182818284590452353602874713526624977572470936999595749669676277240766 -- frequency of 0 is 4 -- frequency of 1 is 3 -- frequency of 2 is 9 -- frequency of 3 is 4 -- frequency of 4 is 7 -- frequency of 5 is 7 -- frequency of 6 is 10 -- frequency of 7 is 12 -- frequency of 8 is 5 -- frequency of 9 is 9 -- -- performance note: On Pentium PRO 200 MHZ, using GNAT 3.11p, Linux 2.0.36, -- 128 MB RAM. No other activity on PC, and for 1,000,000 digits, this -- program will generate about 50 digits each minutes. So, for 1,000,000 -- digits it will take about 13 days. for larger than 1,000,000 you might -- encounter stack overrun, depending on amount of memory you have... -- -- notice the main algorithm is O(n^2). -- with Ada.Text_Io; use Ada.Text_Io; with ada.command_line; use ada.command_line; procedure Dist_E_final is type E_Type is array( Natural range <> ) of Natural; Distribution : array(0..9) of Natural := (others => 0); Num_Of_Digits : Natural; type Sequence_item is record Starts_At, Ends_At, Length : Natural; end record; Sequence: array(0..9) of Sequence_Item := (others=>(0,0,0)); current_Digit, Current_Sequence_Length, Current_Sequence_Start: Natural :=0; procedure Update_Sequence(Next_Digit_Position, next_digit: Natural) is begin if( next_Digit /= Current_Digit) then if( Sequence( current_Digit ).Length < Current_Sequence_Length) then Sequence( current_Digit ).Length := Current_Sequence_Length; Sequence( current_Digit ).Starts_At := Current_Sequence_start; Sequence( Current_Digit ).Ends_At := Next_Digit_Position -1; end if; Current_Digit := Next_Digit; Current_Sequence_Length := 1; Current_Sequence_Start := Next_Digit_Position; else Current_Sequence_Length := Current_Sequence_Length +1; end if; end Update_Sequence; procedure Done_Sequence( Current_Digit_Position: Natural) is begin if( Sequence( current_Digit ).Length < Current_Sequence_Length) then Sequence( current_Digit ).Length := Current_Sequence_Length; Sequence( current_Digit ).Starts_At := Current_Sequence_start; Sequence( Current_Digit ).Ends_At := current_Digit_Position ; end if; end Done_Sequence; begin if( Argument_Count /= 1 ) then Put_Line("usage: dist_e "); return; end if; begin Num_Of_Digits := natural'value( Argument(1)); if( Num_Of_Digits = 0 ) then Put_Line("value for number of digits must be larger than zero"); return; end if; exception when others => Put_Line("Exception. invalid value for number of digits"); return; end; declare -- the algorithm itself is in this block E: E_Type( 1 .. Num_Of_Digits+2 ) := (others=> 1); Carry : Natural; begin Put("2."); for I in E'first .. E'Last-2 loop Carry := 0; for J in reverse E'first .. E'Last loop E(J) := ( E(J) * 10 ) + Carry; Carry := E(J)/(J+1); E(J) := E(J) rem (J+1); end loop; Put(Natural'Image(Carry)(2)); -- print current digit of e Distribution( Carry ) := Distribution( Carry ) + 1; Update_Sequence(I,Carry); end loop; Done_Sequence(E'Last-2); end; New_Line; for I in Distribution'Range loop Put_line("frequency of " & Natural'Image(I) & " is " & natural'Image( Distribution(I) )); end loop; for I in sequence'Range loop if( Sequence(I).Length = 0 ) then Put_Line("Digit "& Natural'Image(I) & " was not seen."); else Put_line("largest concecutive seq of " & Natural'Image(I) &" started at digit " & natural'Image( sequence(I).Starts_at ) & " and ended at digit " & natural'Image( sequence(I).ends_at ) & " of length " & natural'Image( sequence(I).length )); end if; end loop; end Dist_E_final;