Двойная точность в C ++ (или pow (2, 1000))

Question

Я работаю над Project Euler, чтобы освежить свои навыки программирования на C ++ при подготовке к задачам программирования. У нас будет следующий семестр (так как они не позволяют нам использовать Python, бу!).

Я на # 16, и я пытаюсь найти способ сохранить реальную точность для 2¹ °кономИВ

Например:

int main(){
    double num = pow(2, 1000);
    printf("%.0f", num):
    return 0;
}

отпечатков

10715086071862673209484250490600018105614050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Что отсутствует большая часть номеров (из питона):

1015 *>>> 2**1000

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376L

Конечно, я могу написать программу с вкладышем Python 1

sum(int(_) for _ in str(2**1000))

, которая немедленно дает мне результат, но я пытаюсь найти егов C ++.Есть указатели?(ха-ха ...)

Редактировать:

Что-то вне стандартных библиотек для меня ничего не стоит - в этих соревнованиях разрешен только код мертвого дерева, и я, вероятно, не собираюсь печататьиз 10000 строк внешнего кода ...

Answer 1

Если вы просто отслеживаете каждую цифру в массиве символов, это легко. Удвоение цифры является тривиальным, и если результат больше 10, просто вычтите 10 и добавьте перенос к следующей цифре. Начните со значения 1, переберите функцию удвоения 1000 раз, и все готово. С помощью ceil(1000*log(2)/log(10)) вы можете предсказать количество необходимых вам цифр или просто добавить их динамически.

Оповещение о спойлере: Похоже, я должен показать код, прежде чем кто-нибудь мне поверит. Это простая реализация bignum с двумя функциями, Double и Display. Я не сделал это классом в интересах простоты. Цифры сохраняются в формате с прямым порядком байтов, в первую очередь с младшей цифрой.

typedef std::vector<char> bignum;

void Double(bignum & num)
{
    int carry = 0;
    for (bignum::iterator p = num.begin();  p != num.end();  ++p)
    {
        *p *= 2;
        *p += carry;
        carry = (*p >= 10);
        *p -= carry * 10;
    }
    if (carry != 0)
        num.push_back(carry);
}

void Display(bignum & num)
{
    for (bignum::reverse_iterator p = num.rbegin();  p != num.rend();  ++p)
        std::cout << static_cast<int>(*p);
}

int main(int argc, char* argv[])
{
    bignum num;
    num.push_back(1);
    for (int i = 0;  i < 1000;  ++i)
        Double(num);
    Display(num);
    std::cout << std::endl;
    return 0;
}

Answer 2

Возможно, вам нужен указатель здесь (каламбур)

В C ++ вам нужно создать собственную библиотеку bigint, чтобы сделать то же самое, что и в python.

Answer 3

Вам нужна библиотека bignum, такая как эта .

Answer 4

ОБНОВЛЕНИЕ: Я только что перешел на сайт проблемы Эйлера и обнаружил, что проблема 13 касается суммирования больших целых чисел.Итеративный метод может через некоторое время стать очень сложным, поэтому я бы предложил использовать код из Задачи № 13, который вам уже нужно было решить, потому что 2**N => 2**(N-1) + 2**(N-1)

Использование bignums обманываета не решение проблемы.Кроме того, вам не нужно вычислять 2 ** 1000 или что-то подобное, чтобы получить результат.Я дам вам подсказку:

Возьмите первые несколько значений 2 ** N:

0 1 2 4 8 16 32 64 128 256 ...

Теперь запишите для каждого числа сумму его цифр:

1 2 4 8 7 5 10 11 13 ...

Вы должны заметить, что (x~=y означает, что x и y имеют одинаковую сумму цифр)

1+1=2, 1+(1+2)=4, 1+(1+2+4)=8, 1+(1+2+4+8)=16~=7 1+(1+2+4+8+7)=23~=5

Теперь напишите цикл.

Project Euler = Думайте перед вычислением!

Answer 5

C / C ++ работает с основными типами данных.Вы используете double, который имеет только 64 бита для хранения 1000-битного числа.double использует 51 бит для значащих цифр и 11 бит для величины.

Единственное решение для вас - либо использовать библиотеку, подобную bignum, упомянутой в другом месте, либо развернуть свою собственную.

Answer 6

Если вы хотите практиковать подобные вещи, вам нужен арифметический пакет произвольной точности. Вокруг их число: NTL , lip , GMP и MIRACL .

Если вы ищете что-то для Project Euler, вы можете написать свой собственный код для поднятия до власти. Основная идея состоит в том, чтобы хранить ваше большое количество в нескольких маленьких кусочках и реализовывать собственные переносы, заимствования и т. Д. Между кусочками.

Answer 7

Разве pow(2, 1000) не является просто двумя сдвинутыми влево 1000 раз, по сути?Он должен иметь точное двоичное представление в двойном плавающем числе.Для этого не требуется библиотека bignum.