bignum умножение в SBCL

Вчера я попытался выяснить размер нового Мерсенна (http://www.mersenne.org/primes/?press=M74207281) на моем SBCL поле (ст. 1.3.2 (x64), Windows 10, Dell Core i5 8GB RAM) После почти один час я сдался и прервал расчет. Ниже полученного экрана:bignum умножение в SBCL

This is SBCL 1.3.2, an implementation of ANSI Common Lisp. 
More information about SBCL is available at <http://www.sbcl.org/>. 

SBCL is free software, provided as is, with absolutely no warranty. 
It is mostly in the public domain; some portions are provided under 
BSD-style licenses. See the CREDITS and COPYING files in the 
distribution for more information. 

WARNING: the Windows port is fragile, particularly for multithreaded 
code. Unfortunately, the development team currently lacks the time 
and resources this platform demands. 
* (- (expt 2 74207281) 1) 


debugger invoked on a SB-SYS:INTERACTIVE-INTERRUPT in thread 
'#<THREAD "main thread" RUNNING {1002A9BD03}>:' 
    Interactive interrupt at #x100008BD9E. 

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL. 

restarts (invokable by number or by possibly-abbreviated name): 

    0: [CONTINUE] Return from SB-WIN32::SIGINT. 

    1: [ABORT ] Exit debugger, returning to top level. 
1 

(SB-BIGNUM:MULTIPLY-BIGNUMS #<unavailable argument> #<unavailable argument>) 
0] 1

Для меня это было интересно, потому что я пытался то же выражение на Ракетка 6.4, на той же машине, И взял (сравнительно) только 1m08s начать плеваться номера. В Haskell снова на той же машине, с

GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help 

Prelude> 2^74207281 - 1

потребовалось всего 8s начать выставку в цифрах.

Несмотря на то, что это может быть ошибка, кто-нибудь знает, как SBCL выполняет умножение бинарных чисел? Может ли его способ сделать это возможной причиной задержки?

Заранее благодарен!

* EDIT

После Sylvester's комментария, может быть, правильный вопрос: Что мешает большое число от был показан? Да, он действительно большой (версии Racket и Haskell написали его в текстовый файл размером 21 МБ), но кажется, что есть что-то большее, чем его размер, не препятствуя завершению задачи.

источник

2016-02-23 rand

Ответ Sylwester является правильным: умножение bignum выполняется быстро, но * печать * выполняется медленно. Печать очень больших чисел была проблемой производительности в ряде систем (в основном, Lisps, но не только): я подозреваю, что очевидный способ сделать это имеет некоторые ужасные характеристики производительности, но, очевидно, есть более хороший подход, о чем свидетельствует Racket & c , Один из вопросов состоял бы в том, чтобы время полного процесса (в файл, а не на терминал!): Возможно, лучшие системы * начинают * испускать цифры раньше, но получают схожие или, возможно, даже больше времени, чтобы генерировать весь вывод. – tfb

'74207281 * log10 (2) = 22338617.47766583040356636' => 223386180000 знаков, из которых несколько первых 30037641 ... (*' 10 ** 0.47766583040356636 = 3.003764155059042' *). –

@ tfb: есть ли у вас подсказка, как это сделать? Стандартный подход (open-write-line-close) приводит к тому же. – rand

Фактический расчет довольно быстро на моей машине, менее чем на секунду.

(defun make-prime() 
    (declare (optimize (safety 0)(debug 0)(speed 3))) 
    (time (- (expt 2 74207281) 1))) 

(defparameter *prime* (make-prime)) 

;Evaluation took: 
; 0.000 seconds of real time 
; 0.000017 seconds of total run time (0.000015 user, 0.000002 system) 
; 100.00% CPU 
; 1,292 processor cycles 
; 0 bytes consed 
; ==> *PRIME*

Однако печать номера - это совсем другое дело.

источник

2016-02-23 16:55:04 Sylwester

Я пробовал свой код, ведьма принимала почти то же самое время, но когда я выполняю (make-prime), печать снова зависала. Меня заставили подумать, что проблема заключается в умножении бигнама (SB-BIGNUM: MULTIPLY-BIGNUMS), я буду перефразировать мой вопрос. – rand

bignum умножение в SBCL

ответ

Смежные вопросы