[решено] Как обсчитать факториал БОЛЬШИХ чисел... или почему 100!=0 ?

[centaurvv]

Возникла неободимость обсчитать факториал числа 100.
Соорудил нехитрый код, но вот при обсчете числа 100 (а надо и больше) получаю в результате 0!

MsgBox(0,'Факториал', 'Результат: ' & _Factorial(InputBox('Факториал','Введите число:')))

Func _Factorial($int)
Local $i, $res=1
For $i=1 To $int
$res = $res * $i
Next
Return $res
EndFunc


Может кто-нибудь знает как решается данная задача?

[madmasles]

centaurvv,
Здесь посмотрите: Проверка переполнения стека в операциях с вещественными числами (http://autoit-script.ru/index.php?topic=1084.0)

[centaurvv]

Здесь посмотрите: Проверка переполнения стека в операциях с вещественными числами »

как-то не работает :(

MsgBox(0,'Факториал', 'Результат: ' & _Factorial(InputBox('Факториал','Введите число:')))

Func _Factorial($int)
Local $i, $res=1
For $i=1 To $int
$res = $res * $i
ConsoleWrite( $i & '='& $res & '='& _IsOverflow($res) & @CR)
Next
Return $res
EndFunc

Func _IsOverflow($Value)
If $Value - $Value = 0 Then
Return 0
Else
Return 1
EndIf
EndFunc

показывает, что переполнения нет, хотя значения факториала начинает "чудить" уже после 20... а после 65 - вообще сходит на 0!

[madmasles]

centaurvv,
У меня так:$res = 100
For (http://www.autoitscript.com/autoit3/docs/keywords.htm#For) $i = 1 To (http://www.autoitscript.com/autoit3/docs/keywords.htm#To) $res
$res = $res * $i
If (http://www.autoitscript.com/autoit3/docs/keywords.htm#If) $res <= 0 Then (http://www.autoitscript.com/autoit3/docs/keywords.htm#Then)
MsgBox (http://www.autoitscript.com/autoit3/docs/functions/MsgBox.htm)(0, $i, $res)
ExitLoop (http://www.autoitscript.com/autoit3/docs/keywords.htm#ExitLoop)
EndIf (http://www.autoitscript.com/autoit3/docs/keywords.htm#EndIf)
Next (http://www.autoitscript.com/autoit3/docs/keywords.htm#Next)Заканчивается на 19, а если < убрать, то на 64. :)

[SyDr]

centaurvv, если нужен только порядок числа (В числе 100! - 157 десятичных знаков) - можно воспользоваться этим:
MsgBox(0,'Факториал', 'Результат: ' & _Factorial(InputBox('Факториал','Введите число:')))

Func _Factorial($int)
Local $i, $res = 1.0
For $i=1 To $int
$res = $res * $i
Next
Return $res
EndFunc

Если нужно точно само число - следует использовать длинную арифметику.

[kaster]

SyDr, можно воспользоваться этим »
мне кажется, или твоя функция действительно ничем не отличается от той, что привел автор? :)
Если нужно точно само число - следует использовать длинную арифметику. »
AutoIt не поддерживает тип LongInt

Автору могу посоветовать следующее. Т.к. факториалы больших чисел содержат в себе очень много десятичных знаков, лично мне кажется сомнительным использование их все. Если нужно узнать примерный порядок + несколько (возможно не совсем верных) десятичных знаков, то можно воспользоваться следующим приемом
n* = Ln(n!) = Ln(1*2*3*...*n) = Ln(1) + Ln(2) + Ln(3) + ... + Ln(n)
и просто иметь в виду что
n! = exp(n*)
$a = _FalseFact(InputBox('Factorial', 'Etner N'))
MsgBox(0, '', $a[1])

Func _FalseFact($n)
Dim $aTmp[2]
If $n = 0 OR $n = 1 Then Return 1
$tmp = 0
For $i = 1 to $n
$tmp += Log($i)
Next
If $n <= 170 Then
$aTmp[0] = Exp($tmp)
$aTmp[1] = 'The factorial of ' & $n & ' is aproximately ' & $aTmp[0]
Else
$aTmp[0] = $tmp
$aTmp[1] = $N & ' is too big, I can show its factorial only in exponential form. It''s approximately Exp(' & $aTmp[0] & ')'
EndIf
Return $aTmp
EndFunc

[kaster]

[Математика] Как обсчитать факториал БОЛЬШИХ чисел... или почему 100!=0 ? (http://autoit-script.ru/index.php?topic=1321.msg9555#msg9555)

[amel27]

может просто столбиком?.. ;)
ConsoleWrite(_BinaryFacrorial(100) &@CRLF)

; Факториал

Func _BinaryFacrorial($iNum)
Local $res = Binary("0x01")
For $i=1 To $iNum
$res = _BinaryMult($res, Binary("0x"& Hex($i,2)))
Next
Return $res
EndFunc ; ==> _BinaryFacrorial()

; Умножение двух бинарных переменных как чисел (столбиком ;) )

Func _BinaryMult($bin1, $bin2)
If IsBinary($bin1)=0 Or IsBinary($bin2)=0 Then Return SetError(1)

Local $z1 = BinaryLen($bin1), $t1 = DllStructCreate("byte["& $z1 &"]")
DllStructSetData($t1, 1, $bin1)

Local $bin0 = Binary(Chr(0))
For $i=$z1*8-1 To 0 Step -1
If BitAND(DllStructGetData($t1,1,BitShift($i,3)+1),BitRotate(128,-BitAND($i,7))) Then $bin0 = _BinaryAdd($bin0, $bin2)
$bin2 = _Binary2x($bin2)
Next

Return $bin0
EndFunc ; ==> _BinaryMult()

; сложение двух бинарных переменных, как чисел

Func _BinaryAdd($bin1, $bin2)
If IsBinary($bin1)=0 Or IsBinary($bin2)=0 Then Return SetError(1)

Local $z1=BinaryLen($bin1), $z2=BinaryLen($bin2)
Local $z0=$z1, $i, $x=0
If $z2 > $z0 Then $z0 = $z2

Local $tb1 = DllStructCreate("byte["& $z0-$z1+1 &"];byte["& $z1 &"]")
Local $tb2 = DllStructCreate("byte["& $z0-$z2+1 &"];byte["& $z2 &"]")
Local $ti1 = DllStructCreate("byte;byte["& $z0 &"]", DllStructGetPtr($tb1))
Local $ti2 = DllStructCreate("byte;byte["& $z0 &"]", DllStructGetPtr($tb2))
Local $tb0 = DllStructCreate("byte;byte["& $z0 &"]")

DllStructSetData($tb1, 2, $bin1)
DllStructSetData($tb2, 2, $bin2)

For $i = $z0 To 1 Step -1
$x = BitShift($x, 8)
$x += DllStructGetData($ti1, 2, $i) + DllStructGetData($ti2, 2 ,$i)
DllStructSetData($tb0, 2, $x, $i)
Next

If Not(BitAND($x, 0x100)) Then Return DllStructGetData($tb0, 2)
Return Binary(Chr(1)) & DllStructGetData($tb0, 2)
EndFunc ; ==> _BinaryAdd()

; умножение бинарных данных на 2, т.е.
; сдвиг влево с добавлением нулевого бита

Func _Binary2x($bin)
If IsBinary($bin)=0 Then Return SetError(1)
Local $z = BinaryLen($bin), $i, $t, $x=0
If $z=0 Then Return Binary("0x00")

$t = DllStructCreate("byte["& $z &"]")
DllStructSetData($t, 1, $bin)

For $i = $z To 1 Step -1
$x = BitShift($x, 8)
$x = BitOR($x, BitRotate(DllStructGetData($t,1,$i), 1, "W"))
DllStructSetData ($t, 1, $x, $i)
Next

If Not(BitAND($x, 0x100)) Then Return DllStructGetData($t, 1)
Return Binary(Chr(1)) & DllStructGetData($t, 1)
EndFunc ; ==> _Binary2x()


подсказка: для перевода в другую систему счисления нужно добавить вычитание/деление

P.S. проверял этим: Hex Calculator for Programmers and Cryptanalysts (http://www.hexprobe.com/hpmbcalc/index.htm)

[SyDr]

мне кажется, или твоя функция действительно ничем не отличается от той, что привел автор? »
Кажется :) У меня результат заведомо вещественный ($res = 1.0)
AutoIt не поддерживает тип LongInt »
Я не про LongInt, а про реализацию своими руками...

[kaster]

Кажется У меня результат заведомо вещественный ($res = 1.0) »
а, точняк :) но все равно так можно проверять только до 170!
с помощью метода amel27, подсчет 100! заняло 13 сек на моей тачке. Уж не знаю, сколько он будет считать большие значения. Наверное экспоненциально медленнее. А может еще медленнее. Зато без потери точности.
на соседнем форуме я запостил скрипт которым удалось посчитать 100000! за 1,2 сек. Хоть и с потерей точности. Но мне кажется это не принципиально, когда речь идет о таких больших числах. Для справки
100000! = 2.82422940974887*10^456573

[kaster]

amel27, подскажи плз, как перевести полученную строку в десятичное представление? тоже в виде строки, естественно.

[Yashied]

Есть прикольная UDF (http://www.autoitscript.com/forum/index.php?showtopic=83529) для работы с большими числами. 100! считает моментально.

#Include <BigNum.au3>

$n = '1'

For $i = 1 To 100
$n = _BigNum_Mul($n, $i)
Next

ConsoleWrite($n & @CR)

[kaster]

Yashied, да. прикольная либа. я уж думал писать свою для подобных целей :) остановился на сложении длинных чисел. но тут наткнулся на твой пост и решил, что велосипед мне ни к чему :teeth:
1000! считает за 6 сек, 2000! за 27.

[Yashied]

...подскажи плз, как перевести полученную строку в десятичное представление? »

StringFormat('%0.f', $a[1])

[kaster]

Yashied, не совсем понял твой ответ. но и ты наверное не совсем понял мой вопрос, т.к. он относился к посту amel27 в котором он приводил факториал числа в 16-ом представлении. Вот я и хотел чтобы он перевел его каким-то образом в 10-ное. потому как известный мне способ не позволяет это сделать для длинных чисел изза переполнение стека

[amel27]

Вот я и хотел чтобы он перевел его каким-то образом в 10-ное. »а разве велосипед еще актуален?.. :)

гм... на самом деле я не вижу подводных камней (кроме скорости обработки), это же целочисленное деление - при помощи умножения получаем "длинные" степени числа 10 в двоичном представлении, потом вычитанием со сдвигом находим частное и остаток... в любом случае, раньше выходных покодить не получится - на работе загруз

З.Ы. кстати, я привел код для демонстрации того, о чем все итак знают (метод "столбика")... :)

[kaster]

amel27, да не. не парься. твой код проигрывает по времени нахождения факториала тому, что в либе указанный Yashiedом в 1000 раз :) Но там иной принцип. Перевод числа в систему счисления в 10^N.