list - スキームラケットでBig-Intを乗算する

Question

スキームに「big-int」をリストとして実装したので、最初の要素は数値の符号（+または-）であり、次は数値自体の値です。最初は1、次に10などです。 。

例：(+ 0 0 1)は、、100は(- 9 2 3 1)などです-1329。

私が今必要としているのは、この方法で実装されたbig-intの加算、減算、乗算を実装することです。足し算と引き算をしましたが、誰かが掛け算を手伝ってくれませんか？

Answer 1

問題を細かく分割します。まず、Big-intに1桁の整数を掛ける関数を記述します。次に、これを（紙でこれを行う方法をおそらく知っているというGreg Hewgillのヒントを使用して）、Big-intに数字のリストを乗算する関数に拡張します。最後に、これを2つのBig-intを受け入れる関数でラップし、符号を取り除き、前の関数を呼び出します。

これらの関数を開発する前に、これらの関数のテストケースを作成することを強くお勧めします。

Answer 2

これは、big-int乗算に対するよく知られた分割統治アプローチです。

http://ozark.hendrix.edu/~burch/csbsju/cs/160/notes/31/1.html

このアプローチでは、2つの数値を半分に分割し、それらを再帰的に処理します。非常に高速で、長い説明にもかかわらず、実装は簡単です。私はそれを強くお勧めします。他の言語では約10行のコードがすべて必要ですが、スキームではおそらくそれより少なくなります:)。