У меня есть большое число (целое число без знака), которые хранятся в 2-х переменных (как вы можете видеть, высокую и низкую часть числа):Как разделить большие числа?
unsigned long long int high;
unsigned long long int low;
Я знаю, как добавить или вычесть некоторые другие, что-вид переменной.
Но мне нужно разделить такие числа. Как это сделать? Я знаю, я могу вычитать N раз, но, может быть, есть более лучшие решения. ;-)
Язык: C
Да. Это будет связано с изменениями, и я не рекомендую делать это на C. Это один из тех редких примеров, когда ассемблер все еще может доказать свою ценность, легко заставляя вещи работать в сотни раз быстрее (И я не думаю, что я преувеличиваю это)
Я не претендую общую правильность, но следующее должно вам начать:.
(1) Инициализировать результат к нулю.
(2) Сдвиг делителя как можно больше бит влево, не давая ему стать больше дивиденда.
(3) Вычтите смещенный делитель из дивиденда и добавьте его в результат.
(4) Теперь сдвиг делителя вправо до тех пор, пока он еще раз, он меньше оставшегося дивиденда и для каждого сдвига влево, сдвиг влево на один бит.Вернитесь к (3), если условие остановки не выполняется. (Останов условие должно быть что-то вроде «делитель становится нулевым», но я не уверен.)
Это действительно чувствует себя прекрасно, чтобы вернуться к некоторым проблемам РЕАЛ программирования :-)
Условие остановки «когда вы смещались столько раз, сколько вы первоначально сдвигали влево», в противном случае результат не был бы достаточно сдвинут влево. – ChrisW
Вы не рекомендуем переходы в C? Я asm-lover, но C кажется U p к переключению, на мой взгляд. Я очень сомневаюсь, что вы можете написать процедуру ASM для деления, которая в сотни раз быстрее, чем версия C. – Nosredna
Это очень интересно. Можете ли вы указать на какой-то документ, объясняющий математику за этим? (или объясните это сами, если хотите) –
Вы смотрели на любые большие числа библиотек, таких как GNU MP BigNum?
Это слишком «дорого» для этой программы ;-( – 2009-06-19 17:48:17
Хм. Я полагаю, что если у вас есть запас высоты в «высоком», вы можете перенести все на одну цифру, разделить на большее число, затем добавить остаток в верхнюю оставшуюся цифру на низком уровне и делить на нее по номеру, а затем сдвинуть все обратно.
По моим комментариям, мой предыдущий ответ был глупым.
Быстро, моим новым ответом было бы то, что, когда я пытался это сделать в прошлом, он почти всегда включал переключение, потому что это единственная операция, которая может быть применена к нескольким «словам», если хотите, и он выглядит так же, как если бы это было одно большое слово (за исключением необходимости отслеживать бит переноса).
Существует несколько разных подходов к нему, но я не знаю лучшего общего направления, кроме использования смен, если ваше оборудование не имеет специальных операций.
Я думаю, что OP хочет разделить пару (высокую, низкую) на другую (высокую, низкую) пару, что не так просто. – ephemient
Это не то, о чем он говорит. Высокие и низкие части высокого и низкого порядка - это одно слишком большое число, чтобы вставить только один беззнаковый длинный int. –
А, вы правы. Я слишком быстро просмотрел вопрос и предположил, что знаю, что он –
Вот еще одна библиотека, выполняющая 128-битную арифметику. GnuCash: Math128.
Я знаю, я могу вычитать N раз, но, может быть, есть более лучшие решения.
Вычитание N раз может быть медленным, когда N велико.
Лучше (то есть более сложный, но быстрый) будет сменять и вычитать, используя алгоритм, который вы научили делать десятичные числа long division в начальной школе.
[Там также может быть библиотека третьей стороной и/или поддержка компилятора специфичны для таких чисел.]
Замечательное преуменьшение. ITYM «O (n) алгоритмы по 128-битным значениям? AAAAAAAAAAARGH!» –
Да, ICWYM. Дело не в том, что идея - это не стартер, но это не финишер. – ChrisW
Вы могли бы реализовать алгоритм типа BigInt, который выполняет деления на строковых массивах. Создайте 1 строковый массив для каждой высокой, низкой пары и выполните разделение. Сохраните результат в другом массиве строк, а затем преобразуйте обратно в пару с высоким, низким целым.
Поскольку язык C, массив, вероятно, будет массивом символов. Полагайте, что это похоже на «строковый массив», о котором я упоминал выше.
Если бы он принял такой подход, работа в шестнадцатеричном, а не десятичном формате, вероятно, была бы лучше. – Nosredna
Вы можете выполнять сложение и вычитание произвольно больших двоичных объектов с использованием ассемблерных циклов и инструкций «add/subtract with carry (adc/sbb)». Вы можете реализовать другие операции, используя их. Я никогда не расследовал ничего, кроме тех, кто лично.
Если ваш процессор (или ваша библиотека C) имеет быстрое 64-разрядное разделение, вы можете разбить 128-битное разделение на части (так же, как и 32-разрядное разделение на процессорах с 16- бит).
Кстати, есть всевозможные трюки, которые вы можете использовать, если знаете, какие типичные значения будут для дивидендов и делителей. Каков источник этих чисел? Если многие ваши дела могут быть решены быстро, возможно, это нормально, случайный случай занимает много времени.
Кроме того, если вы можете найти случаи, когда приблизительный ответ в порядке, это открывает двери для быстрого приближения.
То же самое, если процессор имеет быстрое 32-разрядное деление или 16-разрядное разделение (используя больше, меньше, штук). – ChrisW
Хорошая точка ChrisW. Если есть какое-то оборудование, которое можно использовать, возможно, стоит попробовать. В настоящее время C выполняет 64-битное разделение на 64 бит? – Nosredna
Вы также хотите разделить * на * большое количество? – balpha