分数変換アルゴリズムの小数点はどのように機能しますか？

Question

私は高調波比のプログラムに取り組んでいます。ユーザーができるようにするためには、様々な比率を接続し、再生する小数点の周波数を高くしたり低くしたりします。

とにかく、このウェブページには、小数点以下の値（比率）を示すJavaScriptアルゴリズムがあります。

http://www.mindspring.com/~alanh/fracs.html

それがどのように動作しますか？私はそれを自分で実装することに興味がありますが、どのように機能するのか分かりません。いくつかの分数を試してみると、多くのオプション（余分な小数点を含むもの）があるので、GCDだけではありません。

編集：このアルゴリズムの質問がもっとプログラマーに適している場合は、私に知らせてください。私はそこに再投稿し、これを削除します。

Answer 1

継続分数を計算して表示しています。連続した小数部の各項は、あなたに大きさの桁違いの別の小数部を与えます。

さらに詳しい説明や使用することができる代替アルゴリズムについては、Algorithm for simplifying decimal to fractionsを参照してください。

Answer 2

あなた進値が最も可能性が高いそれに保存されていると、それは仮数は整数と指数は、あなたが直接それからa/bフォームを抽出することができますので、あまりにも分裂を整数に変換することができますされ、積分バイナリ表現を使用しているとして、あなたはIEEE 754を利用することができます。 32ビット浮動小数点数については、

1 bit sign 
8 bit exponent (with bias 127) 
23+1 bit mantissa (the highest bit is not present in binary but it is 1). 

たとえば、たとえばfloat 3.14159265358979となります。そう

0x40490FDB hex 
0100 0000 0100 1001 0000 1111 1101 1011 bin 
0 10000000 10010010000111111011011 bin 
s exponent  mantissa 

：：私は整数型としてこのフロートコンテンツを読めば、それは次のように保存されている

3.14159265358979 = +1.10010010000111111011011b*2^(10000000b-01111111b) 
3.14159265358979 = +110010010000111111011011b/2^(23-(10000000b-01111111b)) 
3.14159265358979 = +110010010000111111011011b/2^(23-(10000000b-01111111b)) 
3.14159265358979 = +110010010000111111011011b/2^22 
3.14159265358979 = +110010010000111111011011b/2^22 
3.14159265358979 = 13176795/4194304 = 3.1415927410125732421875 

私は私が得た「代数」の方程式としてそれを定義する場合：

float = (sign) (mantissa+2^23)/2^(23-(exp-127)) 

今すぐ適用することができますGCDまたはこれまでに何が欲しい...ここでは簡単C++コード：

void fraction(int &a,int &b,float c) // a/b ~= c 
    { 
    union // convert between float and integer representation 
     { 
     float f32; 
     unsigned int u32; 
     } x; 
    x.f32=c; 
    int s,e; 
    s =x.u32&0x80000000; // sign bit 
    a =x.u32&0x007FFFFF; // mantisa 
    a|=  0x00800000; // add MSB in mantisa (not present in float representation) 
    e =(x.u32>>23)&0xFF; // exponent 
    e-=   0x7F; // exponent bias to make exponent signed again 

    // (optional) divide by 2 while you can (too lazy for GCD as b will be always power of 2 ...) it is better to do it on e instead of b to avoid possible overflows 
    while ((a>=2)&&((a&1)==0)) { a>>=1; e++; } 

    b=1<<(23-e);   // b= 2^(23-exp) 
    if (s) a=-a;   // sign 
    } 

バイナリ指数を得たので、bは常に2の累乗になります。それは代わりにGCDのが2でaを分割するのに十分であることを意味しながら、私たちすることができますし、どちらかの増加指数eまたは分割b最初で唯一の後、通常ははるかに小さい数字にGCDを適用します。これをeに適用して、最終指数がe=<-104,151>でオーバーフローしないようにすると、結果としてbは整数に過ぎず、必要なビット数が大幅に少なくなります。そのような場合bが整数に収まらない場合は逆にするか（aを2倍してeを減算するか、またはbに2を掛けて、仮数部のいくつかの小数点以下を切り捨てるまで...あなたはリンク先のページからここに）

例：

a   b   a/b   c 
13176795/4194304 = 3.141593 ~= 3.141593 
11863283/8388608 = 1.414214 ~= 1.414214 
13573053/8388608 = 1.618034 ~= 1.618034 
    46751/ 128 = 365.242188 ~= 365.242188 

あなたが原因丸め問題を浮きにこれよりも良く得ることができないよりも、文字列や任意の精度でこれを計算している場合を除き。だから、あなたがしたいの精度を浮動（32ビットfloat、64 double、80ビットextended、...）仮数部、指数部を抽出し、a/b

が、それは十分に今明らかであるホープに変換しました。あなたが（文字列/値）からIEEE 754フォームを取得する方法を知りたければ、バイナリへの変換に至ります。小数部分だけが必要であり、これはソースベース（10または2^8,2^16,2^32,...）のターゲットベース（2）による逐次乗算によって行われます。したがって、各反復では値を掛けて、結果の整数部分は新しい桁になり、次の反復には小数部分を使用します...値がゼロでないか、または最大桁数が使用されるまで繰り返します。