Decimal representation of 'e'
-- 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;
Contributed by: Nasser Abbasi
Contributed on: February 21, 1999
License: See Code Header
Back