математика — конверсия большого целого числа & lt; — & gt; двойной в переполнении стека
Я пишу свою собственную длинную арифметическую библиотеку на C ++ для забавы, и она уже довольно закончена, я даже реализовал несколько криптографических алгоритмов с этой библиотекой, но одна важная вещь все еще отсутствует: я хочу преобразовать удваиваемые числа (и числа с плавающей запятой / длинные числа) в мой номер и наоборот. Мои числа представлены в виде массива переменных без знака длинных целых чисел плюс бит знака.
Я пытался найти ответ с помощью Google, но проблема в том, что люди редко когда-либо сами реализуют такие вещи, поэтому я нахожу только вещи о том, как использовать Java BigInteger и т. Д.
Концептуально это довольно просто: я беру мантиссу, сдвигаю ее на количество бит, продиктованных показателем степени, и устанавливаю знак. В другом направлении я обрезаю его так, чтобы он вписывался в мантиссу, и устанавливаю показатель степени в зависимости от моей функции log2.
Но мне трудно разобраться в деталях, я мог бы либо поиграть с некоторыми битовыми паттернами и привести их к двойному результату, но я не нашел элегантного способа достичь этого, либо я мог бы «рассчитать» его, запустив с 2, возвести в степень, умножить и т. д., но это не кажется очень эффективным.
Я был бы признателен за решение, которое не использует библиотечные вызовы, потому что я пытаюсь избежать библиотек для своего проекта, в противном случае я мог бы просто использовать gmp, кроме того, у меня часто есть два решения в нескольких других случаях, одно с использованием встроенного ассемблера, который эффективный и более независимый от платформы, так что любой ответ полезен для меня.
редактировать: я использую uint64_t для своих деталей, но я хотел бы иметь возможность изменять его в зависимости от машины, но я хочу сделать несколько разных реализаций с некоторыми #ifdefs для достижения этой цели.
Решение
Я собираюсь сделать непереносимое предположение здесь, а именно: unsigned long long имеет более точные цифры, чем double, (Это верно для всех современных настольных систем, о которых я знаю.)
Во-первых, преобразуйте наиболее значимые целые числа в unsigned long long, Затем преобразовать это в двойной S, Позволять M быть число целых чисел меньше, чем те, которые используются в этом первом шаге. умножать S от(1ull << (sizeof(unsigned)*CHAR_BIT*M), (Если сдвигается более чем на 63 бита, вам придется разделить их на отдельные сдвиги и выполнить некоторую арифметику). Наконец, если исходное число было отрицательным, вы умножаете этот результат на -1.
Это округляет много, но даже с этим округлением, из-за вышеупомянутого предположения, не теряются никакие цифры, которые в любом случае не будут потеряны при преобразовании в удвоение. Я думаю, что это похоже на то, что сказал Марк Рэнсом, но я не уверен.
Для преобразования из двойного в большой слиток сначала разделите мантиссу на double M и показатель степени в int E, с помощью frexp, Умножение M от UNSIGNED_MAXи сохранить этот результат в unsigned R, Если std::numeric_limits<double>::radix() это 2 (я не знаю, если это для x86 / x64), вы можете легко сдвинуть R оставленный E-(sizeof(unsigned)*CHAR_BIT) биты и все готово. В противном случае результат будетR*(E**(sizeof(unsigned)*CHAR_BIT)) (где ** значит к власти)
Если производительность вызывает беспокойство, вы можете добавить перегрузку в ваш класс bignum для умножения на std::constant_integer<unsigned, 10>, который просто возвращает (LHS<<4)+(LHS<<2), Вы также можете оптимизировать другие константы, если хотите.
Другие решения
Этот пост может помочь вам Уточнение и оптимизация Integer >> asFloat
В противном случае, вы можете иметь представление об алгоритме с таким вопросом Преобразование из неподписанного длинного длинного в плавающее с округлением до ближайшего четного
Вы не говорите явно, но я предполагаю, что ваша библиотека только целочисленная, а беззнаковые длинные 32-битные и двоичные (не десятичные). Конверсия в двойная проста, так что сначала я займусь этим.
Начните с множителя для текущей части; если число положительное, оно будет равно 1,0, если отрицательное, оно будет равно -1,0. Для каждого из беззнаковых длинных целых в вашем bignum умножьте на текущий множитель и добавьте его к результату, затем умножьте ваш множитель на pow(2.0, 32) (4294967296.0) для 32 бит или pow(2.0, 64) (18446744073709551616.0) для 64 бит.
Вы можете оптимизировать этот процесс, работая только с двумя наиболее значимыми значениями. Вам нужно использовать 2, даже если число битов в вашем целочисленном типе больше точности двойного, поскольку число используемый биты в самом значимом значении могут быть только 1. Вы можете сгенерировать множитель, взяв степень 2 на количество пропущенных битов, например, pow(2.0, most_significant_count*sizeof(bit_array[0])*8), Вы не можете использовать битовое смещение, как указано в другом ответе, потому что оно будет переполнено после первого значения.
Чтобы преобразовать из двойного, вы можете получить экспоненту и мантиссу отдельно друг от друга с помощью frexp функция. Мантисса будет иметь значение с плавающей запятой в диапазоне от 0,5 до 1,0, поэтому вам нужно будет умножить ее на pow (2.0, 32) или pow (2.0, 64), чтобы преобразовать в целое число, а затем откорректировать показатель степени на -32 или -64 для компенсации.
Чтобы перейти от большого целого к двойному, просто сделайте это так же, как вы разбираете числа. Например, вы анализируете число «531» как «1 + (3 * 10) + (5 * 100)». Вычислите каждую часть, используя удвоения, начиная с наименее значимой части.
Чтобы перейти от двойного к большому целому, сделайте то же самое, но в обратном порядке, начиная с самой значимой части. Итак, чтобы преобразовать 531, вы сначала увидите, что оно больше 100, но меньше 1000. Вы находите первую цифру, деля ее на 100. Затем вы вычитаете, чтобы получить остаток от 31. Затем найдите следующую цифру, разделив на 10. И скоро.
Конечно, вы не будете использовать десятки (если вы не храните свои большие целые числа в виде цифр). Как именно вы его разбиваете на части, зависит от того, как построен ваш большой целочисленный класс. Например, если он использует 64-разрядные модули, вы будете использовать степени 2 ^ 64 вместо степеней 10.