問題タブ [factorial]

大きな階乗（100までの数）を計算するための次のプログラムに出くわしました。このアルゴリズムで使用される基本的な考え方を誰かに説明してもらえますか？階乗の計算で実装された数学だけを知る必要があります。

xcerionの xml 言語で factorial を実装しようとしています。

私のコードは機能しますが、少し冗長だと思います。

この言語は他の xml 言語と比べてどうですか?

特に変数、選択、ループ、サブルーチン呼び出しの処理。

N 個のアイテムのリストがあり、リストをループしてすべての組み合わせを取得する方法を考えています。double がないので、N をすべて取得する必要があります。注文。余分なメモリは問題ありません。最も単純なアルゴリズムを考えようとしていますが、問題があります。

数の階乗を見つけるための再帰プログラムの複雑さは何nですか？私の勘はそれがそうかもしれないということO(n)です。

自然数の階乗を見つけるプログラムを作成するにはどうすればよいですか？

私は夢中になっています：階乗のRuby関数はどこにありますか？いいえ、チュートリアルの実装は必要ありません。ライブラリの関数が必要です。数学ではありません！

私は疑問を持ち始めています、それは標準ライブラリ関数ですか？

数の階乗を計算したいと思います。私の階乗規則は Prolog ファイルにあり、それを C++ ファイルに接続しています。C++ から Prolog へのインターフェイスの何が問題なのか、誰か教えてもらえますか?

Prolog プロンプトが表示されます。これは、最後の行が行うことです。しかし、次のような階乗計算の結果は得られません。

私は何が欠けていますか？

ありがとう、

私は再帰を練習していますが、なぜこの方法が機能しないように見えるのかわかりません。何か案は？

ありがとう

SICPを読んでいるときに、論理プログラミングの第4.4章に出くわしました。それから私はPrologプログラミング言語を調べ始め、Prologのいくつかの簡単な割り当てを理解しようとしました。Prologは数値計算に問題があるようだとわかりました。

標準のPrologでの階乗の計算は次のとおりです。

私が見つけた問題は、2つの補助変数（CおよびD）、新しい構文（is）を導入する必要があること、および問題が元に戻せないことです（つまり、f(5,X)期待どおりに機能しますが、f(X,120)機能しません）。

素朴に、私は少なくともC is A-1, f(C, D)上記がに置き換えられるかもしれないと期待していますf(A-1,D)が、それでも機能しません。

私の質問は、数値計算ではこの余分な「作業」を行う必要があるのに、他のクエリでは行う必要がないのはなぜですか。

私は、一般的に「何をすべきか」に関する情報は「それをどのように行うか」という質問に答えるには不十分であることを理解しています（そしてSICPはそれについて非常に明確です）。したがって、（少なくともいくつかの）数学の問題に関する宣言的知識は、これらの問題を実際に解決するには不十分です。しかし、それは次の疑問を投げかけます：Prologのこの余分な「もの」は、「何をすべきか」が「それをどのように行うか」に答えるのに十分である問題だけに定式化を制限するのにどのように役立ちますか？

階乗計算を高速化する数学的な「最適な」ベースはありますか？

背景：楽しみのために、私は自分のbignumライブラリを実装しています。（-：これは私の最初の間違いですか？:-)。n階乗（n！）の正確な値（10進数）を出力することにより、内部表現と回帰テストで使用されるさまざまなベースを実験しています。

私のbignumライブラリが整数を表し、乗算を行う方法では、時間は内部表現n​​！の「1」ビットの総数に比例します。内部表現で2、4、8、16、2 ^ 8、2 ^ 30などを使用すると、特定の数値に対してまったく同じ「1」ビットの総数が得られます。

間違いがない限り、基数18で表される階乗（n！）は、基数10または基数16または基数19で表される同じ値よりも「1」ビットが少なくなります。したがって、（原則として）基数を使用します。 18を使用すると、10進数または2進数の2 ^ w基数または基数19を使用するよりも、bignumライブラリの実行速度が速くなります。これは、n！基数10または基数16または基数19よりも基数18で印刷した場合、より短いか、より多くの「末尾ゼロ」があるか、またはその両方です。基数18よりもさらにうまく機能する他の基数はありますか？言い換えれば、nを表すベースはありますか？ベース18よりもさらに少ない「1」ビットで？

これは、「bignumライブラリと素数判定アルゴリズムの便利なベースは何ですか？」の重複ではありません。「2と3の因子がたくさんある、大きな階乗であることがわかっている整数を処理するための最適なベース」は、「小さな因子を持たず、おそらくプライム」。（-：階乗計算を高速化していますか？おそらく他の種類の計算を犠牲にして-私の2番目の間違いですか？:-)

編集：例：

（私は多かれ少なかれ右側の数字をコンマなしで保存し、それにメタデータのオーバーヘッドもあります）。（「ベースを増やすと、特定の数値を表すために使用する「1」ビットが少なくなる」、または「ベースを増やすと、特定の数値を表すために使用するゼロ以外の数字が少なくなる」と考える人もいるかもしれません。例は、それが常に正しいとは限らないことを示しています。）

各桁を小さな整数（「int」または「longint」または「byte」）として格納しています。数字を保存する他の合理的な方法はありますか？私のコンピュータはこれらの整数を2進数で格納していると確信しています。各「1」、「2」、「4」、「8」、および「G」の数字は1つの「1」ビットを使用します。各「3」、「5」、「6」、「9」、および「A」の数字は、2つの「1」ビットを使用します。各「7」および「B」桁は3つの「1」ビットを使用します。各「F」桁は4つの「1」ビットなどを使用します。

この値（16！）の10進数と8進数の両方の表現には、14"1"ビットが必要です。そのため、以前の計算で間違いを犯しました。すべてのnについて、nを表します。8進数では、同じ値を10進数で表すよりも「1」ビットが常に少ないとは限りません。しかし、疑問はまだ残っています。大きな階乗を格納するために必要な1ビットの数が最も少ない他の「最適な」ベースはありますか？

誰かが尋ねます：「あなたはそれらの番号をどのように保存しますか？」さて、それはまさに私の質問です-nの形の数を保存する最良の方法は何ですか！？内部的には、基数10、2の累乗の基数、基数18、またはその他の基数の数字を使用できます。どれが一番いいですか？これらの整数を1Dの数字配列として内部的に格納できますが、すべての桁を格納するには長さが必要です。100を印刷する合理的な方法はありますか？そのような配列なしで10進数で？