小數分數轉換算法，它是如何工作的？

我正在研究一個諧波比率程序，我希望用戶能夠做的一部分是插入各種比率，並且正在播放的小數值頻率顯示更多或更低比率鎖定頻率。小數分數轉換算法，它是如何工作的？

無論如何，在這個網頁上有一個javascript算法來顯示給定小數的小數值（比率）。

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

它是如何工作的？我有興趣自己實施它，但我並不真正瞭解它的功能。如果你嘗試了一些分數，它給了你很多選擇（一些有額外的小數），所以它不完全只是GCD。

編輯：如果這個算法問題會更適合程序員。只是讓我知道，我會重新發布並刪除它。

來源

2017-09-25 sova

你知道，任何浮點值是整數由指數移動...意爲'mantisa/2^exponent'這是對自己的兩個整數之比從浮點數直接得到。然後用GCD分割機器人，你應該得到你想要的。同樣可以通過固定點來完成... – Spektre

@Spektre您的解釋太簡明，我不明白 – sova

我將該註釋轉移到更詳細的示例和C++代碼回答中 – Spektre

它正在計算連續分數並顯示它。連續分數中的每一項都給出了另一個更好的數量級。

請參閱Algorithm for simplifying decimal to fractions瞭解更多詳細說明和替代算法，您可以選擇使用。

來源

2017-09-26 00:45:25 btilly

非常感謝鏈接，它正是我正在尋找 – sova

您可以利用IEEE 754爲您的十進制值是最有可能保存在它和它使用積分二進制表示，其中尾數爲整數，指數可以轉換爲整數除法過這樣你就可以從中直接提取a/b形式。對於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減1或乘以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，80bit的extended，...）提取尾數，指數並轉換爲a/b

希望這是再清楚不過了。如果您想知道如何從（字符串/值）獲得表格，則歸結爲轉換爲二進制。我們只需要小數部分，並且通過在源基底（10或2^8,2^16,2^32,...）中連續乘以目標基底（2）完成。因此，在每次迭代中乘以該值，結果的整數部分爲新數字，並將小數部分用於下一次迭代...重複，直到值不爲零或使用最大位數。

0.123 0b 
0.246 -> 0.0b 
0.492 -> 0.00b 
0.984 -> 0.000b 
1.968 -> 0.0001b 
1.936 -> 0.00011b 
1.872 -> 0.000111b 
1.744 -> 0.0001111b 
1.488 -> 0.00011111b 
0.976 -> 0.000111110b

來源

2017-10-03 07:44:04 Spektre

小數分數轉換算法，它是如何工作的？

回答

相關問題