【UVA – 11809】Floating-Point Numbers【紫书】

【UVA – 11809】Floating-Point Numbers【紫书】

暴力解方程

问题链接:https://vjudge.net/problem/UVA-11809

Solution:

输入都是最大值,对于浮点数,其最大值显然是除了符号位其它位全取1。根据IEEE 754【 https://en.wikipedia.org/wiki/IEEE_754 】或是题上的表述,我们注意到由于浮点后二进制表示下的第一位固定是1【即用二进制表示时,一定是\(0.1xxx…\)】,所以这个1是不存储的,所以如果二进制存储的尾数有m个1,其表示的尾数应该是小数点后有(m + 1)个1的,也就是\((1 – \frac{1}{2^{m + 1}})\)。

所以对于输入aeb得到公式:

\((1 – \frac{1}{2^{m + 1}}) \times 2^{2^e – 1} = a \times 10 ^ b\)

m和e确定是整数,同时注意到m的取值范围更小一些,所以我们可以枚举m来判断等式是否成立。

注意到上式存在\(10^b\)和\(2^{2^e – 1}\)这样很大的形式,我们选择减小数量级,所以方程两边同取10的对数,得到:

\(log_{10}(2^{m + 1} – 1) – (m + 1)log_{10}2 + (2^e – 1)log_{10}2 = log_{10}a \times b\).

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>

using namespace std;

const double EPS = 1e-6;
const int LIM = 256;

int fastPow(int x, int p) {
    int ret = 1;
    while (p) {
        if (p & 1) ret *= x;
        x *= x;
        p >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    const double lg2 = log10(2);
    string str;
    while (cin >> str && str != "0e0") {
        double a;
        int b;
        str[str.find('e')] = ' ';
        stringstream ss;
        ss << str;
        ss >> a >> b;
        double right = log10(a) + b;
        for (int m = 1; m <= 10; m++) {
            int e = round(log10((right + m * lg2 - log10(fastPow(2, m) - 1)) / lg2 + 1) / lg2);
            if (fabs(((1 << e) - 1) * lg2 + log10(fastPow(2, m) - 1) - m * lg2 - right) <= EPS) {
                cout << m - 1 << " " << e << endl;
                break;
            }
        }
    }
    return 0;
}