Текущий архив: 2006.01.22;
Скачать: CL | DM;

Вниз

Факториал больших чисел!   Найти похожие ветки 

← →
Витёк   (2005-12-24 19:18) [0]

Помогите пожалуйста! Как вы счичать фактрориал больших чисел, например факториал 100!??

---

← →
Eraser ©   (2005-12-24 19:20) [1]

> Витёк   (24.12.05 19:18)

Использовать тип Extended. Если не ошибаюсь !n до ~1750 считает.

---

← →
Anatoly Podgoretsky ©   (2005-12-24 19:31) [2]

9,3326215443944152681699238856267e+157

---

← →
uw ©   (2005-12-24 19:35) [3]

Eraser ©   (24.12.05 19:20) [1]
Anatoly Podgoretsky ©   (24.12.05 19:31) [2]

Это все приблизительно. Столбиком надо перемножать строки, имхо.

---

← →
The Only ©   (2005-12-24 20:53) [4]

#include <stdio.h>
#define base 10
#define lbase 1
struct tlong{
int len;
int dig[100];
};
void multl(tlong &n, int a){
int ost=0, work, i;
for (i=0; i<n.len; i++){
  work=a*n.dig[i]+ost;
  n.dig[i]=work%base;
  ost=work/base;
}
while (ost>0){
 n.dig[n.len++]=ost%base;
 ost/=base;
}
}
void printl(tlong &n){
printf("%d", n.dig[n.len-1]);
int i;
for (i=n.len-2; i>=0; i--)
 printf("%*d", lbase, n.dig[i]);
}
tlong res;
int main(){
int i;
int n;
scanf("%d", &n);
res.len=1;
res.dig[0]=1;
for (i=2; i<=n; i++)
 multl(res, i);
printl(res);
return 0;
}

---

← →
palva ©   (2005-12-24 22:25) [5]

Не делают так. Вместо факториала оперируют логарифмом. В некоторые пакеты даже входит стандартная функция, вычисляющая логарифм гамма-функции. И исходник в интернете найти не трудно, правда он на фортране или си.

---

← →
SergP ©   (2005-12-24 22:31) [6]

> Витёк   (24.12.05 19:18)  
> Помогите пожалуйста! Как вы счичать фактрориал больших чисел,
>  например факториал 100!??


Все зависит от того где ты собираешься хранить результат.. А вычислить - не проблема.

---

← →
TStas ©   (2005-12-24 22:35) [7]

>Это все приблизительно. Столбиком надо перемножать строки, имхо.
Именно.

---

← →
Lamer@fools.ua ©   (2005-12-25 01:16) [8]

>Столбиком надо перемножать строки, имхо.

Мне кажется, что лучше перемножать всё-таки числа, а не строки. Или для строк уже тоже ввели операцию умножения? ;o)

>Как вы счичать фактрориал больших чисел, например факториал 100!??

Мы есть считать факториал очэнь балших чисел путём запуска calc.exe.

---

← →
Карелин Артем ©   (2005-12-25 09:02) [9]

unit HugeInts;
interface

const
{$IFDEF HugeInt_64 }

 HugeIntSize = 64;

{$ELSE}{$IFDEF HugeInt_32 }

 HugeIntSize = 32;
{$ELSE}{$IFDEF HugeInt_16 }

 HugeIntSize = 16;
{$ELSE}

 HugeIntSize = 8;
{$ENDIF}{$ENDIF}{$ENDIF}

 HugeIntMSB = HugeIntSize - 1;

type

 HugeInt = array[0..HugeIntMSB] of Byte;

//const
var

 HugeIntCarry: Boolean = False;
 HugeIntDiv0: Boolean = False;

procedure HugeInt_Min(var a: HugeInt); { a := -a }
procedure HugeInt_Inc(var a: HugeInt); { a := a + 1 }
procedure HugeInt_Dec(var a: HugeInt); { a := a - 1 }

procedure HugeInt_Add(a, b: HugeInt; var R: HugeInt); { R := a + b }
procedure HugeInt_Sub(a, b: HugeInt; var R: HugeInt); { R := a - b }
procedure HugeInt_Mul(a, b: HugeInt; var R: HugeInt); { R := a * b }
procedure HugeInt_Div(a, b: HugeInt; var R: HugeInt); { R := a div b }
procedure HugeInt_Mod(a, b: HugeInt; var R: HugeInt); { R := a mod b }

function HugeInt_IsNeg(a: HugeInt): Boolean;
function HugeInt_Zero(a: HugeInt): Boolean;
function HugeInt_Odd(a: HugeInt): Boolean;

function HugeInt_Comp(a, b: HugeInt): Integer; {-1:a< 0; 1:a>}
procedure HugeInt_Copy(Src: HugeInt; var Dest: HugeInt); { Dest := Src }

procedure String2HugeInt(AString: string; var a: HugeInt);
procedure Integer2HugeInt(AInteger: Integer; var a: HugeInt);
procedure HugeInt2String(a: HugeInt; var S: string);

implementation

procedure HugeInt_Copy(Src: HugeInt; var Dest: HugeInt);
{ Dest := Src }
begin

 Move(Src, Dest, SizeOf(HugeInt));
end; { HugeInt_Copy }

function HugeInt_IsNeg(a: HugeInt): Boolean;
begin

 HugeInt_IsNeg := a[HugeIntMSB] and $80 > 0;
end; { HugeInt_IsNeg }

function HugeInt_Zero(a: HugeInt): Boolean;
var
 i: Integer;
begin

 HugeInt_Zero := False;
 for i := 0 to HugeIntMSB do
   if a[i] <> 0 then
     Exit;
 HugeInt_Zero := True;
end; { HugeInt_Zero }

function HugeInt_Odd(a: HugeInt): Boolean;
begin

 HugeInt_Odd := a[0] and 1 > 0;
end; { HugeInt_Odd }

function HugeInt_HCD(a: HugeInt): Integer;
var
 i: Integer;
begin

 i := HugeIntMSB;
 while (i > 0) and (a[i] = 0) do
   Dec(i);
 HugeInt_HCD := i;
end; { HugeInt_HCD }

procedure HugeInt_SHL(var a: HugeInt; Digits: Integer);
{ Перемещение байтов переменной "Digits" в левую часть,

байты "Digits" будут "ослабевать" в MSB-части.
LSB-часть заполняется нулями. }
var
 t: Integer;
 b: HugeInt;
begin

 if Digits > HugeIntMSB then
   FillChar(a, SizeOf(HugeInt), 0)
 else if Digits > 0 then
 begin
   Move(a[0], a[Digits], HugeIntSize - Digits);
   FillChar(a[0], Digits, 0);
 end; { else if }
end; { HugeInt_SHL }

procedure HugeInt_SHR(var a: HugeInt; Digits: Integer);
var
 t: Integer;
begin

 if Digits > HugeIntMSB then
   FillChar(a, SizeOf(HugeInt), 0)
 else if Digits > 0 then
 begin
   Move(a[Digits], a[0], HugeIntSize - Digits);
   FillChar(a[HugeIntSize - Digits], Digits, 0);
 end; { else if }
end; { HugeInt_SHR }

procedure HugeInt_Inc(var a: HugeInt);
{ a := a + 1 }
var

 i: Integer;
 h: Word;
begin

 i := 0;
 h := 1;
 repeat
   h := h + a[i];
   a[i] := Lo(h);
   h := Hi(h);
   Inc(i);
 until (i > HugeIntMSB) or (h = 0);
 HugeIntCarry := h > 0;
{$IFOPT R+ }
 if HugeIntCarry then
   RunError(215);
{$ENDIF}
end; { HugeInt_Inc }

procedure HugeInt_Dec(var a: HugeInt);
{ a := a - 1 }
var
 Minus_1: HugeInt;
begin

 { самый простой способ }
 FillChar(Minus_1, SizeOf(HugeInt), $FF); { -1 }
 HugeInt_Add(a, Minus_1, a);
end; { HugeInt_Dec }

procedure HugeInt_Min(var a: HugeInt);
{ a := -a }
var
 i: Integer;
begin

 for i := 0 to HugeIntMSB do
   a[i] := not a[i];
 HugeInt_Inc(a);
end; { HugeInt_Min }

function HugeInt_Comp(a, b: HugeInt): Integer;
{ a = b: ==0; a > b: ==1; a < b: ==-1 }
var

 A_IsNeg, B_IsNeg: Boolean;
 i: Integer;
begin

 A_IsNeg := HugeInt_IsNeg(a);
 B_IsNeg := HugeInt_IsNeg(b);
 if A_IsNeg xor B_IsNeg then
   if A_IsNeg then
     HugeInt_Comp := -1
   else
     HugeInt_Comp := 1
 else
 begin
   if A_IsNeg then
     HugeInt_Min(a);
   if B_IsNeg then
     HugeInt_Min(b);
   i := HugeIntMSB;
   while (i > 0) and (a[i] = b[i]) do
     Dec(i);
   if A_IsNeg then { оба отрицательные! }
     if a[i] > b[i] then
       HugeInt_Comp := -1
     else if a[i] < b[i] then
       HugeInt_Comp := 1
     else
       HugeInt_Comp := 0
   else { оба положительные } if a[i] > b[i] then
       HugeInt_Comp := 1
     else if a[i] < b[i] then
       HugeInt_Comp := -1
     else
       HugeInt_Comp := 0;
 end; { else }
end; { HugeInt_Comp }

procedure HugeInt_Add(a, b: HugeInt; var R: HugeInt);
{ R := a + b }
var

 i: Integer;
 h: Word;
begin

 h := 0;
 for i := 0 to HugeIntMSB do
 begin
   h := h + a[i] + b[i];
   R[i] := Lo(h);
   h := Hi(h);
 end; { for }
 HugeIntCarry := h > 0;
{$IFOPT R+ }
 if HugeIntCarry then
   RunError(215);
{$ENDIF}
end; { HugeInt_Add }



---

← →
Карелин Артем ©   (2005-12-25 09:03) [10]

procedure HugeInt_Sub(a, b: HugeInt; var R: HugeInt);
{ R := a - b }
var

 i: Integer;
 h: Word;
begin

 HugeInt_Min(b);
 HugeInt_Add(a, b, R);
end; { HugeInt_Sub }

procedure HugeInt_Mul(a, b: HugeInt; var R: HugeInt);
{ R := a * b }
var

 i, j, k: Integer;
 A_end, B_end: Integer;
 A_IsNeg, B_IsNeg: Boolean;
 h: Word;
begin

 A_IsNeg := HugeInt_IsNeg(a);
 B_IsNeg := HugeInt_IsNeg(b);
 if A_IsNeg then
   HugeInt_Min(a);
 if B_IsNeg then
   HugeInt_Min(b);
 A_End := HugeInt_HCD(a);
 B_End := HugeInt_HCD(b);
 FillChar(R, SizeOf(R), 0);
 HugeIntCarry := False;
 for i := 0 to A_end do
 begin
   h := 0;
   for j := 0 to B_end do
     if (i + j) < HugeIntSize then
     begin
       h := h + R[i + j] + a[i] * b[j];
       R[i + j] := Lo(h);
       h := Hi(h);
     end; { if }
   k := i + B_End + 1;
   while (k < HugeIntSize) and (h > 0) do
   begin
     h := h + R[k];
     R[k] := Lo(h);
     h := Hi(h);
     Inc(k);
   end; { while }
   HugeIntCarry := h > 0;
{$IFOPT R+}
   if HugeIntCarry then
     RunError(215);
{$ENDIF}
 end; { for }
 { если все хорошо... }
 if A_IsNeg xor B_IsNeg then
   HugeInt_Min(R);
end; { HugeInt_Mul }

procedure HugeInt_DivMod(var a: HugeInt; b: HugeInt; var R: HugeInt);
{ R := a div b  a := a mod b }
var

 MaxShifts, s, q: Integer;
 d, e: HugeInt;
 A_IsNeg, B_IsNeg: Boolean;
begin

 if HugeInt_Zero(b) then
 begin
   HugeIntDiv0 := True;
   Exit;
 end { if }
 else
   HugeIntDiv0 := False;
 A_IsNeg := HugeInt_IsNeg(a);
 B_IsNeg := HugeInt_IsNeg(b);
 if A_IsNeg then
   HugeInt_Min(a);
 if B_IsNeg then
   HugeInt_Min(b);
 if HugeInt_Comp(a, b) < 0 then
   { a<b; нет необходимости деления }
   FillChar(R, SizeOf(R), 0)
 else
 begin
   FillChar(R, SizeOf(R), 0);
   repeat
     Move(b, d, SizeOf(HugeInt));
     { сначала вычисляем количество перемещений (сдвигов) }
     MaxShifts := HugeInt_HCD(a) - HugeInt_HCD(b);
     s := 0;
     while (s <= MaxShifts) and (HugeInt_Comp(a, d) >= 0) do
     begin
       Inc(s);
       HugeInt_SHL(d, 1);
     end; { while }
     Dec(s);
     { Создаем новую копию b }
     Move(b, d, SizeOf(HugeInt));
     { Перемещаем (сдвигаем) d }
     HugeInt_ShL(d, S);
     { Для добавление используем e = -d, это быстрее чем вычитание d }
     Move(d, e, SizeOf(HugeInt));
     HugeInt_Min(e);
     Q := 0;
     { пока a >= d вычисляем a := a+-d и приращиваем Q}
     while HugeInt_Comp(a, d) >= 0 do
     begin
       HugeInt_Add(a, e, a);
       Inc(Q);
     end; { while }
     { Упс!, слишком много вычитаний; коррекция }
     if HugeInt_IsNeg(a) then
     begin
       HugeInt_Add(a, d, a);
       Dec(Q);
     end; { if }
     HugeInt_SHL(R, 1);
     R[0] := Q;
   until HugeInt_Comp(a, b) < 0;
   if A_IsNeg xor B_IsNeg then
     HugeInt_Min(R);
 end; { else }
end; { HugeInt_Div }

procedure HugeInt_DivMod100(var a: HugeInt; var R: Integer);
{ 256-тиричное деление - работает только с

положительными числами: R := a mod 100; a:= a div 100; }
var

 Q: HugeInt;
 S: Integer;
begin

 R := 0;
 FillChar(Q, SizeOf(Q), 0);
 S := HugeInt_HCD(a);
 repeat
   r := 256 * R + a[S];
   HugeInt_SHL(Q, 1);
   Q[0] := R div 100;
   R := R mod 100;
   Dec(S);
 until S < 0;
 Move(Q, a, SizeOf(Q));
end; { HugeInt_DivMod100 }

procedure HugeInt_Div(a, b: HugeInt; var R: HugeInt);
begin

 HugeInt_DivMod(a, b, R);
end; { HugeInt_Div }

procedure HugeInt_Mod(a, b: HugeInt; var R: HugeInt);
begin

 HugeInt_DivMod(a, b, R);
 Move(a, R, SizeOf(HugeInt));
end; { HugeInt_Mod }

procedure HugeInt2String(a: HugeInt; var S: string);

 function Str100(i: Integer): string;
 begin
   Str100 := Chr(i div 10 + Ord("0")) + Chr(i mod 10 + Ord("0"));
 end; { Str100 }
var

 R: Integer;
 Is_Neg: Boolean;
begin

 S := "";
 Is_Neg := HugeInt_IsNeg(a);
 if Is_Neg then
   HugeInt_Min(a);
 repeat
   HugeInt_DivMod100(a, R);
   Insert(Str100(R), S, 1);
 until HugeInt_Zero(a) or (Length(S) = 254);
 while (Length(S) > 1) and (S[1] = "0") do
   Delete(S, 1, 1);
 if Is_Neg then
   Insert("-", S, 1);
end; { HugeInt2String }

procedure String_DivMod256(var S: string; var R: Integer);
{ 10(00)-тиричное деление - работает только с

положительными числами: R := S mod 256; S := S div 256 }
var
 Q: string;
begin

 FillChar(Q, SizeOf(Q), 0);
 R := 0;
 while S <> "" do
 begin
   R := 10 * R + Ord(S[1]) - Ord("0");
   Delete(S, 1, 1);
   Q := Q + Chr(R div 256 + Ord("0"));
   R := R mod 256;
 end; { while }
 while (Q <> "") and (Q[1] = "0") do
   Delete(Q, 1, 1);
 S := Q;
end; { String_DivMod256 }

procedure String2HugeInt(AString: string; var a: HugeInt);
var

 i, h: Integer;
 Is_Neg: Boolean;
begin
 FillChar(a, SizeOf(HugeInt), 0);
 if AString = "" then
   AString := "0";
 Is_Neg := AString[1] = "-";
 if Is_Neg then
   Delete(Astring, 1, 1);
 i := 0;
 while (AString <> "") and (i <= HugeIntMSB) do
 begin
   String_DivMod256(AString, h);
   a[i] := h;
   Inc(i);
 end; { while }
 if Is_Neg then
   HugeInt_Min(a);
end; { String2HugeInt }

procedure Integer2HugeInt(AInteger: Integer; var a: HugeInt);
var
 Is_Neg: Boolean;
begin

 Is_Neg := AInteger < 0;
 if Is_Neg then
   AInteger := -AInteger;
 FillChar(a, SizeOf(HugeInt), 0);
 Move(AInteger, a, SizeOf(Integer));
 if Is_Neg then
   HugeInt_Min(a);
end; { Integer2HugeInt }

end.

---

← →
Anatoly Podgoretsky ©   (2005-12-25 10:09) [11]

uw ©   (24.12.05 19:35) [3]
Про точность речи не было.

---

← →
uw ©   (2005-12-25 10:21) [12]

Anatoly Podgoretsky ©   (25.12.05 10:09) [11]

А у меня тоже есть калькулятор с видом "Инженерный"! Впрочем, что обсуждать, когда у The Only все работает :)

---

← →
uw ©   (2005-12-25 10:32) [13]

Я тут посмотрел-посмотрел, сравнил The Only © с Карелин Артем © и пришел к выводу: на сколько же С короче Паскаля! Все, теперь буду ваять исключительно на С.

---

← →
Separator ©   (2005-12-25 10:42) [14]

Что-то я не пойму, а чем плох обычный метод:

function Fact(N: Integer): Integer;
var
   i: Integer;
begin
   Result:= 1;
   for i:= 2 to N do
       Result:= Result * i
end;

---

← →
uw ©   (2005-12-25 10:46) [15]

Так, подставь 100, и все сразу станет понятно.

---

← →
Карелин Артем ©   (2005-12-25 10:58) [16]

> uw ©   (25.12.05 10:32) [13]

И что же ты сравнил??? Только длину кода? :)))))))))))))))

---

← →
Kerk ©   (2005-12-25 11:03) [17]

Ну и мои 5 копеек
http://kladovka.net.ru/index.cgi?pid=list&rid=53

---

← →
uw ©   (2005-12-25 11:15) [18]

Карелин Артем ©   (25.12.05 10:58) [16]
И что же ты сравнил??? Только длину кода? :)))))))))))))))

Ну! Нет, у тебя, конечно, солиднее, слов нет. А у него даже ошибки есть - длина массива коротковата, там. Но все равно - теперь только на С.

---

← →
Amoeba ©   (2005-12-28 14:51) [19]

> palva ©   (24.12.05 22:25) [5]
> Не делают так. Вместо факториала оперируют логарифмом. В
> некоторые пакеты даже входит стандартная функция, вычисляющая
> логарифм гамма-функции. И исходник в интернете найти не
> трудно, правда он на фортране или си.

Есть и на паскале: библиотека ESBMaths (бесплатно, с исходниками)

---

← →
Amoeba ©   (2005-12-28 14:55) [20]

Там же напрямую считается факториал для N<=1754

---

← →
Gero ©   (2005-12-28 15:54) [21]

> Там же напрямую считается факториал для N<=1754

А если мне 1755 надо, тогда как?

---

← →
Ega23 ©   (2005-12-28 15:56) [22]

> Но все равно - теперь только на С.
>


А в чём разница???

---

← →
Sha ©   (2005-12-28 16:03) [23]

> uw ©   (25.12.05 10:32) [13]
> на сколько же С короче Паскаля! Все, теперь буду ваять исключительно на С.

А на Паскале-то короче будет:

function Factorial(n: cardinal): string;
var
 s: string;
begin;
 s:=ReverseString(IntToStr(n));
 Result:="1";
 while (s[1]<>"0") or (Length(s)>1) do begin;
   Result:=MulString(Result,s);
   DecString(s);
   end;
 Result:=ReverseString(Result);
 end;


---

← →
uw ©   (2005-12-28 16:34) [24]

Sha ©   (28.12.05 16:03) [23]
А на Паскале-то короче будет:

Мастер! А мне все равно приходится на С и С++ писать - программирую микроконтроллеры, сигнальные процессоры. Сейчас к тому же придется сопровождать и на VC++ 6. Ё-о, какая хрень!

---

← →
Карелин Артем ©   (2005-12-28 17:55) [25]

> uw ©   (28.12.05 16:34) [24]

Так под них есть паскаль и васик

---

← →
uw ©   (2005-12-28 22:15) [26]

Карелин Артем ©   (28.12.05 17:55) [25]

Здорово! Ну, дай мне ссылку для какого-нибудь прибора из ряда
C8051F1xx, ADSP-BF53x, MSP430, ADSP-21xx... И еще, порекомендуй заказчика, который бы принял у меня работу, выполненную на васике...
да и на паскале тож.

---

← →
uw ©   (2005-12-28 22:22) [27]

Кстати, я заподозрил, что мое "ё-о" было неправильно понято. Оно относилось не к С или С++. Эти языки мне очень нравятся, когда они используются для программирования этих самых МК. Да и VC++ хорош при программировании драйверов. А вот для прикладных задач уже Делфи очень хороши, а VC рядом с ними - "ё-о".

---

Страницы: 1 вся ветка

Текущий архив: 2006.01.22;
Скачать: CL | DM;

Наверх

Память: 0.56 MB
Время: 0.03 c