4

私は楽しみのために C++ で独自の長い算術ライブラリを作成していますが、すでにかなり完成しています。そのライブラリでいくつかの暗号化アルゴリズムを実装しましたが、重要なことが 1 つまだ欠けています: double (および float/long double) を私の番号とその逆。私の数値は、unsigned long int と符号ビットの可変サイズの配列として表されます。

私はグーグルで答えを見つけようとしましたが、問題は、人々がそのようなことを自分で実装することはめったにないということです.

概念的には、かなり簡単です。仮数を取り、指数によって決まるビット数だけシフトし、符号を設定します。他の方向では、仮数部に収まるように切り捨て、log2 関数に応じて指数を設定します。

しかし、詳細を理解するのに苦労しています。いくつかのビットパターンをいじってダブルにキャストすることもできましたが、それを達成するためのエレガントな方法が見つからなかったか、開始して「計算」できました2、べき乗、乗算などがありますが、あまり効率的ではないようです。

プロジェクトのライブラリを回避しようとしているため、ライブラリ呼び出しを使用しないソリューションをいただければ幸いです。それ以外の場合は gmp を使用することもできました。効率的で、プラットフォームに依存しないものなので、どちらの答えも役に立ちます。

編集:私は自分のパーツに uint64_t を使用していますが、マシンに応じて変更できるようにしたいと考えていますが、それを達成するためにいくつかの #ifdefs を使用していくつかの異なる実装を行っても構わないと思っています.

4

4 に答える 4

2

ここでは、移植性のない仮定を立てます。つまり、unsigned long longよりも正確な数字があるということdoubleです。(これは、私が知っているすべての最新のデスクトップ システムに当てはまります。)

まず、最上位の整数を に変換しunsigned long longます。次に、それを double に変換しSます。Mその最初のステップで使用されたものよりも少ない整数の数にしましょう。Sを掛け(1ull << (sizeof(unsigned)*CHAR_BIT*M)ます。(63 ビット以上をシフトする場合は、それらを別々のシフトに分割し、いくつかの算術演算を行う必要があります) 最後に、元の数値が負の場合、この結果に -1 を掛けます。

これはかなり丸められますが、この丸めでも、上記の仮定により、double への変換で失われることのない桁は失われません。これは Mark Ransom が言ったことと同様のプロセスだと思いますが、確かではありません。

double から biginteger に変換するには、まず仮数を にdouble M、指数を にint E、 を使用して分離しfrexpます。を掛けMてUNSIGNED_MAX、その結果を に格納しunsigned Rます。が 2 の場合std::numeric_limits<double>::radix()(x86/x64 用かどうかはわかりません)、ビット単位で簡単にR左にシフトでき、完了です。E-(sizeof(unsigned)*CHAR_BIT)それ以外の場合、結果は次のようになりますR*(E**(sizeof(unsigned)*CHAR_BIT))(ここで**は、べき乗を意味します)

パフォーマンスが問題になる場合は、bignum クラスにオーバーロードを追加して を乗算することができます。std::constant_integer<unsigned, 10>これは単純に を返します(LHS<<4)+(LHS<<2)。必要に応じて、他の定数も同様に最適化できます。

于 2012-09-07T19:04:23.303 に答える
1

このブログ投稿は、Integer>>asFloat の明確化と最適化に役立つ可能性があります

それ以外の場合は、この SO question Converting from unsigned long long to float with round tonearest evenでアルゴリズムのアイデアをまだ得ることができます

于 2012-09-07T19:50:26.887 に答える
0

big integer から double に変換するには、数値を解析するのと同じ方法で行います。たとえば、数値「531」を「1 + (3 * 10) + (5 * 100)」として解析します。最下位の部分から始めて、double を使用して各部分を計算します。

double から big integer に変換するには、同じ方法で行いますが、逆に最も重要な部分から始めます。したがって、531 を変換するには、まず 100 より大きく 1000 より小さいことがわかります。最初の桁を 100 で割って求めます。次に、減算して 31 の余りを求めます。次に、10 で割って次の桁を求めます。すぐ。

もちろん、10 を使用することはありません (大きな整数を数字として格納しない限り)。正確にどのように分割するかは、大きな整数クラスがどのように構築されているかによって異なります。たとえば、64 ビット単位を使用している場合は、10 の累乗ではなく 2^64 の累乗を使用します。

于 2012-09-07T18:53:32.310 に答える
0

明示的には言いませんが、ライブラリは整数のみで、符号なし long は 32 ビットおよびバイナリ (10 進数ではない) であると想定しています。doubleへの変換は簡単なので、最初に取り組みます。

現在のピースの乗数から始めます。数値が正の場合は 1.0、負の場合は -1.0 になります。bignum の unsigned long int ごとに、現在の乗数を掛けて結果に加算し、乗数pow(2.0, 32)に 32 ビットの場合は (4294967296.0) pow(2.0, 64)、64 ビットの場合は (18446744073709551616.0) を掛けます。

最も重要な 2 つの値のみを使用することで、このプロセスを最適化できます。最上位値で使用されるビット数は 1 しかない可能性があるため、整数型のビット数が double の精度よりも大きい場合でも、2 を使用する必要があります。 2からスキップされたビットの数pow(2.0, most_significant_count*sizeof(bit_array[0])*8)。最初の値の後にオーバーフローするため、別の回答にあるようにビットシフトを使用することはできません。

double から変換するには、関数で指数と仮数を分離して取得できますfrexp。仮数は 0.5 から 1.0 の間の浮動小数点値になるため、pow(2.0, 32) または pow(2.0, 64) を掛けて整数に変換し、指数を -32 または-64 を補正します。

于 2012-09-07T18:56:23.133 に答える