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