Алгоритм Burnikel и Ziegler «RecursiveDivision» для деления больших чисел имеет два предварительных условия, одно из которых: «Частное Q должно умещаться в n цифр». Как узнать, выполняется ли предварительное условие, не выполняя сначала деление?
Как проверить предварительное условие для деления Бурникеля и Циглера?
Ответы (1)
Насколько мне известно, Бюрникель-Циглер имеет другое предварительное условие. Учитывается количество конечностей (в моем случае конечность — это 32-битное целое число без знака). Если вы разделите n
конечностей на m
конечностей, в результате получится не более n-m+1
конечностей (я предполагаю, что тот же расчет верен для количества цифр). Так что это может дать вам подсказку.
Но в моем коде BigInteger
предварительное условие:
function ShouldUseBurnikelZiegler(LSize, RSize: Integer): Boolean;
begin
// http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-November/023493.html
Result := (RSize >= BigInteger.BurnikelZieglerThreshold) and
((LSize - RSize) >= BigInteger.BurnikelZieglerOffsetThreshold);
end;
LSize
— размер левого операнда (делимого), а RSize
— размер правого операнда (делителя) в конечностях. Пороги для моего кода:
const
BurnikelZieglerThreshold = 91;
BurnikelZieglerOffsetThreshold = 5;
Вы должны (экспериментально) найти пороги для своего собственного кода.
В моем коде я уже дал ссылку , где Я понял.
Мне известно, что не все знакомы с Pascal (или Object-Pascal), но я думаю, что приведенный выше фрагмент кода достаточно удобочитаем, чтобы понять суть.
LSize - RSize
). Другой порог — это абсолютный размер (в конечностях). Если размеры (или различия в размерах) превышают этот порог, то деление Бурникеля-Циглера происходит быстрее, чем обычное деление (Кнут, также известное как базовый случай). Burnikel-Ziegler имеет довольно много накладных расходов, поэтому он не быстрее для небольших целых чисел (или даже для небольших BigIntegers). Это имеет смысл только для больших BigInteger. Вы также можете использовать количество цифр, если хотите, но тогда пороговые значения в несколько раз больше, чем для конечностей. продолжение в следующем комментарии.
- person Rudy Velthuis; 02.04.2017
{$IFDEF PUREPASCAL}
и либо {$ELSE}
, либо {$ENDIF}
. Обратите внимание, что я использую 16-битные целые числа (Word или UInt16 в языке Delphi), потому что использование 32-битных целых чисел дает некоторые 64-битные промежуточные результаты, а они медленные в 32-битном Паскале (но не на ассемблере). 16-битный способ оказался намного быстрее в моей настройке.
- person Rudy Velthuis; 03.04.2017
divmnu.c
, который можно легко перевести на Eiffel или любой другой язык. Он также использует 16-битные целые числа (32-битные конечности, разделенные на 16-битные фрагменты), IIRC. Он очень хорошо переводит алгоритм Кнута. Например. в Hacker's Delight: hackersdelight.org/hdcodetxt/divmnu.c.txt.
- person Rudy Velthuis; 03.04.2017
n
цифры наm
цифры, результат будет состоять не более чем изn-m+1
цифр. Вы можете проверить это на нескольких рассчитанных вручную примерах. - person Rudy Velthuis   schedule 31.03.2017