Meertens数
Posted feedbacks - Smalltalk
Squeak Smalltalk で。
1 GHz PowerPC 上で、10 桁で 8 分弱でした。もうすこし速くできるかも…。もっとも、例によって無名関数と付随する環境のコピーを作ってから逐次実行するなんちゃって再帰なので、通常の Smalltalk で普通に再帰するのよりかなり遅いです。骨董品並みのマシンスペックとあわせて、割り引いておいてください(^_^;)。
1 GHz PowerPC 上で、10 桁で 8 分弱でした。もうすこし速くできるかも…。もっとも、例によって無名関数と付随する環境のコピーを作ってから逐次実行するなんちゃって再帰なので、通常の Smalltalk で普通に再帰するのよりかなり遅いです。骨董品並みのマシンスペックとあわせて、割り引いておいてください(^_^;)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | | nDigits primes goeOf results max rec |
nDigits := 10.
primes := Integer primesUpTo: 72.
goeOf := [:ds |
ds := ds allButFirst: (ds, {1} findFirst: [:ea | ea > 0]) - 1.
(1 to: ds size) inject: 1 into: [:res :idx |
((primes at: idx) raisedTo: (ds at: idx)) * res]].
results := OrderedCollection new.
max := 10 raisedTo: nDigits.
rec := [:digits |
digits size = nDigits
ifTrue: [
| mm goe |
mm := digits reverse polynomialEval: 10.
goe := goeOf value: digits.
mm = goe ifTrue: [results add: goe]]
ifFalse: [
0 to: 9 do: [:digit |
| next |
next := digits copyWith: digit.
(goeOf value: next) < max ifTrue: [rec copy fixTemps value: next]]]].
^{nDigits. [rec copy fixTemps value: #()] timeToRun. results asArray}
"=> #(10 464170 #(81312000)) "
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]