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

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)

- AutoIt (http://forum.oszone.net/forumdisplay.php?f=103)

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

Возникла неободимость обсчитать факториал числа 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

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

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

Код:

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!

centaurvv,
У меня так:

Код:

$res = 100

For $i = 1 To $res

    $res = $res * $i

    If $res <= 0 Then

        MsgBox(0, $i, $res)

        ExitLoop

    EndIf

Next

Заканчивается на 19, а если < убрать, то на 64. :)

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

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

SyDr,

Цитата:

Цитата SyDr

можно воспользоваться этим »

мне кажется, или твоя функция действительно ничем не отличается от той, что привел автор? :)

Цитата:

Цитата 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

может просто столбиком?.. ;)

Код:

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

Цитата:

Цитата kaster

мне кажется, или твоя функция действительно ничем не отличается от той, что привел автор? »

Кажется :) У меня результат заведомо вещественный ($res = 1.0)

Цитата:

Цитата kaster

AutoIt не поддерживает тип LongInt »

Я не про LongInt, а про реализацию своими руками...

Цитата:

Цитата SyDr

Кажется У меня результат заведомо вещественный ($res = 1.0) »

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

Код:

100000! = 2.82422940974887*10^456573

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

Есть прикольная UDF для работы с большими числами. 100! считает моментально.

Код:

#Include <BigNum.au3>



$n = '1'



For $i = 1 To 100

    $n = _BigNum_Mul($n, $i)

Next



ConsoleWrite($n & @CR)

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

Цитата:

Цитата kaster

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

Код:

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

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

Цитата:

Цитата kaster

Вот я и хотел чтобы он перевел его каким-то образом в 10-ное. »

а разве велосипед еще актуален?.. :)

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

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

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