Pow точность с unsigned long

Итак, я пытаюсь сделать pow (x, y). Где x и y - беззнаковые длинные, а результат сохраняется в беззнаковом длинном. Этот результат будет меньше, чем 2 ^ 63, поэтому я смогу это сделать. Но поскольку он возвращает число с плавающей запятой, я получаю неточные результаты для больших чисел. Есть ли способ получить точный результат без использования внешних библиотек, таких как bignum? Я знаю, что мог бы просто сделать x*x в Y раз, но я стараюсь избегать этого, потому что пытаюсь сделать свою программу быстрее.


c precision pow
person LifeisHard    schedule 22.10.2015    source источник
comment
Где твой код? Вероятно, вам нужно округлить число с плавающей запятой до ближайшего целого числа.   -  person owacoder    schedule 22.10.2015
comment
pow делает exp(y*log(x)), что быстро, но есть проблемы с точностью.   -  person Breaking not so bad    schedule 22.10.2015
comment
Это может вас заинтересовать: en.wikipedia.org/wiki/Exponentiation_by_squaring   -  person user4520    schedule 22.10.2015
comment
I Проблема в том, что это не 1 число, а 37. answer = pow(a, b);   -  person LifeisHard    schedule 22.10.2015
comment
Я не помечал как дубликат, потому что вы не знали, как это сделать в первую очередь, но вы можете посмотреть на это: stackoverflow.com/questions/101439/   -  person Emilien    schedule 22.10.2015
comment
под Этот результат будет меньше 2^63, вы имеете в виду, что значения x и y таковы, что результат будет достаточно мал, или вы подразумеваете модульную арифметику? Если вы проверите, что x равно 0 или 1, у вас должно быть не более 61 умножения с циклом грубой силы, даже не заслуживающим оптимизации.   -  person chqrlie    schedule 22.10.2015
comment
Если вы пытаетесь возвести целое число в целочисленную степень, чтобы получить целочисленный результат, то, вероятно, лучший вариант — не преобразовывать в число с плавающей запятой для получения приблизительного результата. Я уверен, что очень небольшое количество поисков найдет вам несколько реализаций интегральной степенной функции. Даже если вы не можете его найти, написать его не так уж и сложно...   -  person twalberg    schedule 22.10.2015
comment
почему бы тогда просто не вычислить unsigned long pow(unsigned long x, unsigned long y); как y кратное x?   -  person Paul Evans    schedule 23.10.2015

Ответы (3)


arrow_upward
6
arrow_downward

Функция pow возвращает двойное значение, у которого есть проблемы с точностью, и когда вы будете приводить его к длинному значению, вы наверняка получите проблему с точностью. Насколько я знаю, если вы не используете библиотеку, невозможно получить точный результат, используя только функцию pow.

Вы также можете посмотреть Возведение в степень путем возведения в квадрат, а также посмотреть барак-манос answer, где вы можете попытаться реализовать свою собственную функцию pow как

unsigned long long pow(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y > 0)
    {
        if (y & 1)
            res *= x;
        y >>= 1;
        x *= x;
    }
    return res;
}
person Rahul Tripathi    schedule 22.10.2015
comment
Эффективен ли этот метод для очень больших чисел? Типа 10000^10000(x^y)? потому что я хочу все время держать значение ниже 2 ^ 63-1. Итак, я пытаюсь максимально приблизиться к 2 ^ 63-1, затем я выполню свой расчет в этой части, возьму результат и перенесу его в следующий расчет, пока мой y не станет достаточно маленьким, чтобы выполнить мой расчет немедленно. - person LifeisHard; 22.10.2015
comment
@LifeisHard: 10000^10000 не меньше, чем 2^63, так что у вас будут другие проблемы с этим. Помимо того факта, что вам потребуется (приблизительно) 125 других вселенных, чтобы хранить все эти цифры. - person Jongware; 22.10.2015
comment
@Jongware: 10000^10000 больше, чем 2 ^ 63, но все равно легко поместится на веб-странице, хотя и не в комментарии: за 1 следует 40000 0s. - person chqrlie; 22.10.2015
comment
@chqrlie: ... 10000^10, согласно калькулятору Google, равно 1e+40. Это 10³¹ Гб — немного многовато для веб-страницы, а обсуждаемое число на целый гугол больше. - person Jongware; 22.10.2015
comment
@Jongware Если бы ОП на самом деле говорил об этом числе как о количестве байтов, которые нужно сохранить, то да, это действительно было бы довольно большим для хранения на веб-странице. Однако, рассматривая это просто как число, 10 000 000 000 000 000 000 000 000 000 000 000 000 000, даже написанное от руки с запятыми, вполне уместится практически на любой веб-странице... - person twalberg; 22.10.2015
comment
@Jongware: @twalberg: LifeisHard пишет: 10000^10000(x^y). Я предполагаю, что он имеет в виду x=10000 и y=10000, но формула довольно запутанная. 10000^10000 в базе 10 имеет ровно 40001 цифру. Это намного больше, чем 10000^10, почти в 1000 раз больше цифр, но все равно умещается на веб-странице. - person chqrlie; 22.10.2015
comment
Создание функции unsigned long long pow(unsigned long long x,unsigned int y) ... — хороший способ вызвать неприятные ошибки. C не имеет сигнатур для функций с тем же именем. Это маскирует/скрывает стандартный `double pow( double, double ); функция. - person Andrew Henle; 22.10.2015

arrow_upward
1
arrow_downward

pow по определению неточен. Он использует exp(y*log(x)) как способ эмулировать x ^ y. Если вам нужна полная точность, вам нужно либо использовать внешнюю библиотеку, либо создать собственную версию pow.

person magisch    schedule 22.10.2015

arrow_upward
-1
arrow_downward

Я не уверен в вашем коде. Но я думаю, ваш код такой

unsigned long x,y;
x=...//
y=...//

unsigned long res=pow(x,y);

Это неправильно. Потому что pow() всегда возвращает тип double.

double pow(double x, double y)

вот почему у вас есть номер двойного типа.

Чтобы получить правильный номер, вы можете сделать следующее:

    unsigned long x,y;
    x=...//
    y=...//

    unsigned long res=(unsigned long)pow(x,y);
person Newaz Hossain    schedule 22.10.2015
comment
Это не решает проблему OP: поскольку он возвращает число с плавающей запятой, я получаю неточные результаты для больших чисел. - person Jongware; 22.10.2015
comment
@Jongware, вы уверены, что значение res является числом с плавающей запятой. - person Newaz Hossain; 22.10.2015
comment
Ваше объяснение сбивает с толку: пока pow правильно объявлено через #include <math.h>, первый вариант не представляет проблемы, преобразование в unsigned long является неявным, и компилятор будет генерировать правильный код. И наоборот, если pow не объявлено, добавление явного преобразования ничего не меняет: компилятор предположит, что функция имеет прототип int pow(int,int);, и сгенерированный код будет совершенно неправильным. - person chqrlie; 26.10.2015