UVa 11809 - Floating-Point Numbers

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址

Solution

很難理解的一題，大概是英文障礙…

要計算如何用它給的方式記小數點，尾數和指數部分各需要幾個位元。

所以要先了解它是如何算的，指數部分較沒問題，直接將二進位轉成十進位就是次方數，例如:

111111 十進位是 $2^6-1=63$，所以這個小數點就是 $M \times 2^{63}$。接著是尾數的部分(M):

題意有寫到 $\frac{1} {2} \le m \lt 1$ ，再看了別人的題解後，大概是有內建一位尾數，所以計算時最小就是 $2^{-1}$ 開始往上加，例如:

.11111111(八個 1) 十進位是 $2^{-1}+2^{-2}+\ldots+2^{-8}+2^{-9} = 0.998046875$ ，因為第一個是內建的。

接著其輸入 AeB 為科學記號，為了要查詢其所需要用到的位數，我們要先建表。
把 E (1~30), M (0~9) 所能表示出的小數點依照其指數和尾數(以 10 為底的)記下來。

而這部分先須從二進位轉換成十進位:
(這邊的 e,m 為使用的位數)
依剛剛所提指數部分: $2^e-1$

尾數部分利用等比級數: $\frac {2^{-1}( 1-2^{-1-m} )}{1-2^{-1}} = 1-2^{-1-m}$

$x = mantissa \times 2^{exponent}$ ，因數字太大要取 log，剛好以 10 為底可以得到待會科學記號的指數。

$logx = log((1-2^{-1-m})\times2^{(2^e-1)}) = log_{10}(1-2^{-1-m})+ log_{10}(2^{(2^e-1)})$

最後則是用成十進位的科學記號:
(接下來的 e,m 與剛意義不同)
e = floor(x) 可取出其指數部分。
$m = 10^{x-e}$，$0\le x-e \lt 1$ , $1 \le m \lt 10$

$FP = m \times 10^e$

最後只要查詢輸入的指數(B)所配對的 e ，還有與它最接近的 m (需處理精度問題)，就可得知其位數。

科學記號wiki

Code

UVa 11809

#include<cstdio>
#include<cmath>
#define EPS 1e-6

int main()
{
	int E[10][31];
	double M[10][31], mantissa, exp, x;
	
	for (int i = 0; i < 10; i++)
		for (int j = 1; j < 31; j++)
		{
			mantissa = 1 - pow(2, -1 - i);//1-2^(-1-m),內建一位尾數
			exp = pow(2, j) - 1;//2^e-1
			x = log10(mantissa) + exp*log10(2);//從二進位轉到十進位後，取log
			
			double e, m;//用成科學記號
			e = floor(x);
			m = pow(10, x - e);//10^(x-e)，剩下小數點的部分(剛取過log)，1 <= m < 10
			E[i][j] = e;
			M[i][j] = m;
		}

	char num[50];
	while (fgets(num, 50, stdin))
	{
		if (num[0] == '0'&&num[2] == '0')
			break;

		num[17] = ' ';//15 digits after the decimal point.

		int n;
		sscanf(num, "%lf%d", &mantissa, &n);
		for (int i = 0; i < 10; i++)
			for (int j = 1; j < 31; j++)
				if (n == E[i][j] && std::abs(mantissa - M[i][j]) < EPS)//指數相同，小數點誤差小於EPS
				{
					printf("%d %d\n", i, j);
					break;
				}
	}

	return 0;
}