Каков наиболее эффективный способ хранения и работы с числом с плавающей запятой с 1 000 000 значащих цифр в C?

Question

Я пишу утилиту для вычисления π до миллиона цифр после десятичной дроби. Какой 32-разрядный или 64-разрядный настольный компьютер является наиболее эффективным способом хранения и работы с таким большим числом с точностью до миллионной цифры?

уточнение: язык будет C.

Answer 1

Забудьте с плавающей запятой, вам нужны битовые строки, которые представляют целые числа

Это занимает чуть меньше 1/2 мегабайта на номер. «Эффективный» может означать несколько вещей. Пространственно-эффективный? Время эффективное? Легко программируется с?

Ваш вопрос помечен с плавающей точкой , но я совершенно уверен, что вам вообще не нужна плавающая точка. Вся идея с плавающей запятой заключается в том, что наши данные известны только нескольким значащим цифрам, и даже знаменитые физические и химические константы точно известны лишь нескольким или двум цифрам. Поэтому имеет смысл сохранить разумное количество цифр, а затем просто записать показатель степени.

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

Что вам действительно нужно, так это строка битов. Это просто массив удобных типов. Я предлагаю <stdint.h> и просто использовать uint32_t[125000] (или 64), чтобы начать. На самом деле это может быть хорошим использованием более непонятных констант из этого заголовка, которые выбирают размеры битов, которые быстры на данной платформе.

Чтобы быть более конкретным, нам нужно знать больше о ваших целях. Это для практики на определенном языке? Для некоторого исследования в теории чисел? Если последнее, почему бы просто не использовать язык, который уже поддерживает язык Bignum, такой как Ruby?

Тогда проблема с хранилищем - чужая. Но, если вы действительно хотите реализовать пакет с большим числом, то я мог бы предложить использовать 4-битные строки bcd или даже 8-битные строки ascii с печатными цифрами, просто потому, что все будет проще писать и отлаживать и максимальная эффективность пространства и времени может не иметь большого значения.

Answer 2

Я бы порекомендовал хранить его как массив коротких целых, по одному на цифру, а затем тщательно писать вспомогательные классы для сложения и вычитания частей числа. В конечном итоге вы перейдете от этого массива целых к плавающим и обратно, но вам нужен «идеальный» способ хранения числа - поэтому используйте его точное представление. Это не самый эффективный способ с точки зрения пространства, но миллион целых не очень большой.

Все зависит от того, как вы используете представление. Решите, как вы собираетесь «работать» с этим числом, и напишите несколько полезных служебных функций.

Answer 3

Если вы хотите допустить вычисление числа pi в шестнадцатеричном, а не в десятичном виде, есть очень симпатичный алгоритм , который позволяет вычислять заданную шестнадцатеричную цифру, не зная предыдущих цифр. Таким образом, это означает, что вам не нужно хранить (или иметь возможность выполнять вычисления) миллионные цифры.

Конечно, если вы хотите получить nth десятичную цифру, вам нужно знать все шестнадцатеричные цифры с точностью до этой точности, чтобы выполнить базовое преобразование, поэтому в зависимости от ваших потребностей, это не может спасти вас (если вообще что-нибудь) в конце концов.

Answer 4

Вы можете сохранить его десятичные цифры в виде текста в файле и преобразовать его в массив.

Answer 5

Попробуйте PARI / GP , см. Википедия .

Answer 6

Если вы пишете это не для удовольствия и / или обучения, я бы рекомендовал использовать такую ​​библиотеку, как GNU Multiprecision . Посмотрите на тип данных mpf_t и связанные с ним функции для хранения чисел с плавающей точкой произвольной точности.

Если вы просто делаете это для развлечения / обучения, то представляйте числа в виде массива chars, в котором каждый элемент массива хранит одну десятичную цифру. Вам придется реализовать длинное сложение, длинное умножение и т. Д.

Answer 7

ИМО, любой программист произвольной точности требует понимания базового преобразования. Это решает в любом случае две проблемы: возможность вычислить число в шестнадцатеричных числах и преобразовать материал в десятичное представление, а также найти оптимальный контейнер.

Доминирующим ограничением является количество правильных битов в инструкции умножения.
В Javascript всегда есть точность 53 бита, это означает, что массив Uint32Array с числами, имеющими максимум 26 бит, может быть обработан непосредственно. (потеря 6 бит на слово).

В 32-битной архитектуре с C / C ++ можно легко получить A * B mod 2 ^ 32, предлагая базовый элемент из 16 бит. (Они могут быть распараллелены во многих архитектурах SIMD, начиная с MMX). Также каждый 16-битный результат может содержать 4-значные десятичные числа (тратя около 2,5 бит) на слово.

Answer 8

Однажды я работал над приложением, которое использовало действительно большие числа (но не нуждалось в хорошей точности). То, что мы сделали, это сохранили числа в виде логарифмов, так как вы можете хранить довольно большое число как log10 внутри int.

Подумайте об этом, прежде чем прибегать к вставке битов или некоторым сложным представлениям битов.

Я не слишком хорош со сложной математикой, но я считаю, что есть решения, которые элегантны при сохранении чисел с миллионами битов точности.