Bertel Lund Hansens hjemmeside

Beregning af e

          1     1     1

 e = 1 + --- + --- + --- ...

          1!    2!    3!

Metoden kan ikke konkurrere med nogle af de helt specialiserede programmer, men den er nem at programmere uden dybtgående kendskab til programmering, og den kan bruges til mange slags beregninger.

Princippet består i at hver variabel oprettes som et array af heltal. Lad os sige at hvert enhed kan rumme 10 præcise cifre - altså tal op til (men ikke med) 10 milliarder. Så skal man blot lave funktioner med de nødvendige regningsarter hvor man regner i 10-milliarder-talsystemet.

Addition, subtraktion er nemme nok. De har køretiden O(n). Derimod kræver multiplikation og division en mere kompleks rutine som vistnok får køretiden O(n^2).

Til beregning af e kan man imidlertid nøjes med addition af to lange tal samt division af et langt tal med et almindeligt tal. Desuden bemærker man at addition frembringer et resultat som i værste tilfælde kun er ét ciffer større end de to addender, og at division altid vil formindske tallet. Derfor skal enhederne kun have plads til ét ekstra ciffer i reserve.

Hvis man vil have rigtig mange decimaler, kommer man på et tidspunkt til at lave lang division - nemlig når en almindelig variabel ikke kan rumme det præcise (reciprokke) fakultetstal mere. I PHP på denne server har jeg konstateret at der regnes præcist når jeg sætter blokstørrelsen til 12 cifre. Det bliver for lidt når man kommer til fakultetstallet af 10^12. Det er cirka 10^11'565'705'518'103. potens. Der går nok et stykke tid før beregninger i den størrelsesorden kan afvikles i ikke-astronomisk tid.

Antallet af cifre registreres i variablen $blocks. $max er en variabel som får værdien 10^$blocks.

Først sættes variablerne $e og $rec_fact til at have værdien array(1,0,0,0 ...). Det svarer til "1". $rec_fact er den reciprokke værdi af fakultetstallet fordi vi så kan addere det direkte i stedet for at lave en kompliceret lang division.

Her er divisionsrutinen. Den svarer til den metode man bruger når man regner i hånden:

function long_divide ($number,$n) {
   GLOBAL $max;
   $rest=0;
   foreach ($number as $nr => $block) {
      $tal=$block+$rest*$max;
      $number[$nr]=floor($tal/$n);
      $rest=$tal%$n;
   }
   return $number;
}

Den sidste rest forsvinder i det blå. Den påvirker nemlig kun decimaler ud over dem der er bedt om.

Her er additionsrutinen. Den svarer også til den manuelle algoritme:

function long_add ($number,$addend) {
   GLOBAL $max;
   $blocks=count($number);
   $mente=0;
   for ($nr=$blocks-1; $nr>=0; --$nr) {
      $sum=$number[$nr]+$addend[$nr]+$mente;
      $number[$nr]=$sum%$max;
      $mente=$sum/$max;
   }
   $number[0]+=$mente;
   return $number;
}

Vi adderer enhederne bagfra. Bemærk at vi her skal have den allersidste mente med.

Nu kan vi oprette en $n-løkke hvor $rec_fact divideres med $n og derefter adderes til $e. Vi skal blot have en bremse indbygget så løkken ikke løber løbsk. Bremsen består i princippet af at vi husker den gamle værdi af $e og så sammenligner med den nye. Når de to er ens, er der ingen grund til at regne videre.

Men i stedet for hver gang at sammenligne alle enhederne, kan vi nøjes med at sammenligne én af dem, nemlig den første til at begynde med. Når de to første er ens, sammenligner vi nummer 2, og så fremdeles, og når de to sidste er ens, er vi færdige.

Her er main-rutinen. Læg mærke til hvordan der regnes videre på det samme (reciprokke) fakultetstal i stedet for at begynde forfra hver gang:

$e=array_fill(0,$blocks,0);
$e[0]=1;
$rec_fact=$e;
$old_e=array(0);

// ---------------- Compute ----------------

$n=0;
$compare=0;
$start = microtime(1);
while ($compare<=$blocks) {
   ++$n;
   $old_e=$e;
   $rec_fact=long_divide($rec_fact,$n);
   $e=long_add($e,$rec_fact);
   if ($e[$compare]==$old_e[$compare]) ++$compare;
}
echo " Beregningstid i sekunder: "
  .number_format(microtime(1)-$start,6)."<br>"
  ." Sidste fakultetstal: $n";
display($e);

Ved udskriften skal man huske noget vigtigt - nemlig at fylde enhederne ud med 0'er. Hvis der f.eks. skal være 10 cifre i hver blok, så skal en blok med værdien "18876" udskrives som "0000018876". Det gælder dog ikke den første.

Noter til dem der ikke er vant til PHP:

  1. Notationen er som udgangspunkt C-notation.
  2. Variable starter med $, og de har ingen fast type.
  3. Divisioner udregnes altid som float. Det er derfor der bruges floor() i divisionsrutinen.
  4. foreach ($number as $nr => $block)
    vil i f.eks. Python svare til: 
    for nr,block in enumerate(number):
  5. $array1=$array2
    kopierer værdien af $array2 til $array1. I Python (og måske andre sprog) ville det reultere i at de to variable henviste til samme værdi. Der ville man altså være nødt til at gennemløbe alle blokkene.

Her er hele koden.

PS. I Python kan man udnytte at det kan regne med uendeligt store tal i nogle beregninger. Det giver et meget hurtigere program.