факториалы больших чисел Опции

[sqrt]

Требуется найти факториалы всех чисел от 1 до 100. Стандартный цикл не канает, т.к. в longint не влезет факториал ста... Есть подозрение что это можно реализовать рекурсией, но как? Что делать???

[volvo]

sqrt
Рекурсия вызывает переполнение при n = 14
То, что может помочь - длинночисленная арифметика. Смотри здесь

[sqrt]

Пасибо, попробую умножение длинных чисел.

[Digitalator]

Есть подозрение что это можно реализовать рекурсией

А каким образом рекурсия вообще может спасти от переполнения? помойму она только приводит к переполнению

[sqrt]

Что-то у меня ничего не получается... может кто поможет написать? Я делал цикл на умножение длинного числа на короткое [1;100] и сразу же печать в текстовый файл каждого факториала.. Но, видимо туплю - не получается ничего.

[sqrt]

Люди! Что я неправильно делаю? Подскажите, плиз...

Код

program factorial;
const  _md=1000;
    _osn=10000;
type    t_long=array[0.._md] of integer;
    p_long=^t_long;
var    a,c:p_long;
    i,k:integer;

begin
a^[0]:=1;
a^[1]:=1;
for k:=1 to 15 do
    begin
       write(k, ' => ');
    for i:=1 to a^[0] do
 begin
 c^[i+1]:=(longint(a^[i])*k+c^[i]) div _osn;
 c^[i]:=(longint(a^[i])*k+c^[i]) mod _osn;
 end;
    if c^[a^[0]+1]>0 then c^[0]:=a^[0]+1 else c^[0]:=a^[0];
    for i:=0 to c^[0]+1 do begin a^[i]:=c^[i]; write(a^[i]); end;
    writeln('');
    end;
readln(i);
end.

пытаюсь найти факториалы от 1цы до 15 - нифига неправильно

Сообщение отредактировано: sqrt - 21.12.2004 16:50

[volvo]

sqrt
Держи правильную программу (она пишет факториалы чисел 1 - 100 в файл "fact_100.txt"):

Код

Const
 Base = 10000; { system base }
 maxLen = 300; { max digits length }

 { digits delimiter for output, '|' for example }
 DigitSep: String = '';

     { getting max of (Base-1) and (MaxLen), so }
     { we could store length in the array item  }
     Max = (Base-1+MaxLen+Abs(Base-1-MaxLen)) Div 2;

Type
 Digit = 0..Pred(Base);            { type for the digit storing }
 Inter = 0..Pred(Base)*Succ(Base); { type for the temporary use }
 Index = 0..maxLen;                { type for the digis number storing }

 { type for the very long integer (VLI) storing }
 { item #0 stores number of digits in VLI       }
 LargeInt = Array [0..MaxLen] Of 0..Max;


{ called when overflow detected }
Procedure Overflow(Const s : String);
 Begin
   WriteLn('Error:'#1310'Overflow when making ', s);
   Halt(1)
 End;

{ LargeInt initialization by (x) number --  A := x }
{ ASSERT: using LongInt instead of Digit, }
{ guessing that MaxLongInt >= Base-1 }
Procedure Init(Var A: LargeInt; x: LongInt);
 Var i: Index;
 Begin
   FillChar(A, SizeOf(A), 0); i := 0;
   Repeat
     If i = maxLen Then Overflow('Init');
     Inc(i); A[i] := x mod Base;
     x := x div Base
   Until x = 0;
   A[0] := i
 End;


{ A := A * x }
Procedure MulDigit(Var A: LargeInt; x: Digit);
 Var i: Index; T: Inter;
 Begin
   T := 0;
   For i := 1 To A[0] Do
     Begin
       T := Inter(A[i])*x + T;
       A[i] := T mod Base; T := T div Base
     End;
   If T > 0 Then
     Begin
       If A[0] = maxLen Then Overflow('MulDigit');
       Inc(A[0]); A[A[0]] := T
     End
 End;


{ A := n! }
Procedure Fact(Var A: LargeInt; n: LongInt);
 Var T: LargeInt; i: LongInt;
 Begin
   Init(T, 1);
   For i := 2 To n Do
     MulDigit(T, i);
   A := T
 End;

{ Printing LargeInt  --  Write(A) }
Procedure Print(Var f: Text;
         Const A: LargeInt);
 Var
   i: Index; k: Digit; s: String;
 Begin
   Str(Base - 1, s); k := Length(s);
   Write(f, A[A[0]]);
   For i := A[0]-1 DownTo 1 Do
     Begin
       Str(A[i], s);
       While Length(s) < k Do s := '0' + s;
       Write(f, DigitSep, S)
     End
 End;

{ main program }
Var
 f: LargeInt; i: LongInt;
 out: Text;
begin
 Assign(out, 'fact_100.txt');
 ReWrite(out);

 For i := 1 To 100 do
   Begin
     Fact(f, i);
     Print(out, f); writeln(out); writeln(out)
   End;

 Close(out)
end.

[sqrt]

volvo
Спасибо большое!

[xds]

shr offtop,1
В детстве баловался:

Код

program FuckToReal;

const DataSize = 16384;
     ResultSize = 60000;

type PResult = ^TResult;
    TResult = array[0..0] of Char;

var Data: array[0..DataSize - 1] of Word;
   Result: PResult;
   Digits, N: Integer;
   SymbolIndex, i: Word;

begin
 GetMem(Result, ResultSize);
 Write('N>');
 Readln(N);
 FillChar(Data, SizeOf(Data), 0);
 Data[0] := 1;
 Digits := 1;
 Write('Calculating... ');

 { Calulating of factorial by long binary multiplication }
 asm
   push bp
   mov bp,N
 @@NextPass:
   push ds
   pop es
   lea si,Data
   mov di,si
   cld
   xor bx,bx
   mov cx,Digits
 @@NextDigit:
   lodsw
   mul bp
   add ax,bx
   adc dx,0
   stosw
   mov bx,dx
   loop @@NextDigit
   or bx,bx
   jz @@Exit
   inc Digits
   mov cx,1
   jmp @@NextDigit
 @@Exit:
   dec bp
   cmp bp,1
   ja @@NextPass
   pop bp
 end;
 Writeln('Done');
 Write('Converting...  ');

 { Building a decimal representation of long binary number }
 SymbolIndex := ResultSize;
 asm
   push bp
   mov bp,Digits
   dec bp
   shl bp,1
   lea bp,Data[bp]
   les di,Result
   add di,ResultSize-1
   mov bx,10
   std
 @@NextSymbol:
   xor dx,dx
   mov si,bp
   cmp [si],bx
   jae @@NextDigit
   sub bp,2
 @@NextDigit:
   lodsw
   div bx
   mov [si+2],ax
   cmp si,offset Data
   jae @@NextDigit
   mov al,dl
   add al,'0'
   stosb
   dec SymbolIndex
   cmp bp,offset Data
   jae @@NextSymbol
   pop bp
 end;
 Writeln('Done');
 for i := SymbolIndex to ResultSize - 1 do Write(Result^[i]);
 Writeln;
 FreeMem(Result, ResultSize);
end.

Считала 10000! (с точностью до едениц) на Pentium 100 MHz за 37 секунд.