Как проверить предварительное условие для деления Бурникеля и Циглера?

Алгоритм Burnikel и Ziegler «RecursiveDivision» для деления больших чисел имеет два предварительных условия, одно из которых: «Частное Q должно умещаться в n цифр». Как узнать, выполняется ли предварительное условие, не выполняя сначала деление?


person jjj    schedule 31.03.2017    source источник
comment
Смотрите мой ответ. Вкратце: если вы разделите n цифры на m цифры, результат будет состоять не более чем из n-m+1 цифр. Вы можете проверить это на нескольких рассчитанных вручную примерах.   -  person Rudy Velthuis    schedule 31.03.2017


Ответы (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), но я думаю, что приведенный выше фрагмент кода достаточно удобочитаем, чтобы понять суть.

person Rudy Velthuis    schedule 31.03.2017
comment
Спасибо. Ваш ответ помог мне взглянуть на проблему по-другому. B&Z использовала термин «цифры» для обозначения того, что сейчас другие называют конечностями. Предварительное условие вписаться в n цифр кажется мне больше похожим на пост-условие; это всегда будет верно для обычной математики, и то же самое должно быть верно для реализации bigInteger, верно? Кстати, что такое BurnikelZieglerOffsetThreshold концептуально? - person jjj; 02.04.2017
comment
OffsetThreshold — это разница в размерах (в моем коде LSize - RSize). Другой порог — это абсолютный размер (в конечностях). Если размеры (или различия в размерах) превышают этот порог, то деление Бурникеля-Циглера происходит быстрее, чем обычное деление (Кнут, также известное как базовый случай). Burnikel-Ziegler имеет довольно много накладных расходов, поэтому он не быстрее для небольших целых чисел (или даже для небольших BigIntegers). Это имеет смысл только для больших BigInteger. Вы также можете использовать количество цифр, если хотите, но тогда пороговые значения в несколько раз больше, чем для конечностей. продолжение в следующем комментарии. - person Rudy Velthuis; 02.04.2017
comment
Неверно, что это верно для нормальных целых чисел. Точные пороги зависят от того, насколько быстро происходит ваше обычное (базовое) деление. Вы можете только экспериментально определить пороги для своего кода, просто сравнив обычное деление по Бурникелю-Циглеру и проверив, при каких размерах (и различиях в размерах) при Бурникеле-Циглере становится быстрее. Я сделал это для своего кода. Другие реализации BigInteger также сделали это и достигли других пороговых значений. Опять же, BZ быстрее только для не слишком маленьких BigInteger из-за накладных расходов кода. - person Rudy Velthuis; 02.04.2017
comment
Большой. Я понимаю, что в зависимости от количества конечностей существует кроссовер над головой и скоростью. Я не знал о разнице в размерах между делимым и делителем. Спасибо. Что вы имеете в виду под моим Неверно, что это справедливо для обычных целых чисел? Что это такое и что такое обычные целые числа? (Кстати, я должен использовать термин конечности, я не работаю с основанием 10.) - person jjj; 03.04.2017
comment
Не могли бы вы поделиться своим кодом паскаля для вашего базового деления? У меня самые тяжелые времена, когда я переводил алгоритм Кнута D в Eiffel. - person jjj; 03.04.2017
comment
Эйфель? Вау, это хороший язык, но я не видел ничего подобного уже много лет. В любом случае, взгляните на: github.com/rvelthuis/BigNumbers /blob/master/Source/ и просто игнорируйте ассемблерные части. Каждая функция имеет чистую версию Pascal, разделенную {$IFDEF PUREPASCAL} и либо {$ELSE}, либо {$ENDIF}. Обратите внимание, что я использую 16-битные целые числа (Word или UInt16 в языке Delphi), потому что использование 32-битных целых чисел дает некоторые 64-битные промежуточные результаты, а они медленные в 32-битном Паскале (но не на ассемблере). 16-битный способ оказался намного быстрее в моей настройке. - person Rudy Velthuis; 03.04.2017
comment
FWIW, в Интернете есть файл с именем divmnu.c, который можно легко перевести на Eiffel или любой другой язык. Он также использует 16-битные целые числа (32-битные конечности, разделенные на 16-битные фрагменты), IIRC. Он очень хорошо переводит алгоритм Кнута. Например. в Hacker's Delight: hackersdelight.org/hdcodetxt/divmnu.c.txt. - person Rudy Velthuis; 03.04.2017
comment
@JimmyJohnson: FWIW, как насчет голосования или принятия? Так работает этот сайт. - person Rudy Velthuis; 04.04.2017
comment
Я проголосовал за ваш ответ, но, похоже, у меня меньше определенного количества очков репутации, поэтому голоса могут записываться, но не изменять общедоступную оценку публикации. Если я каким-то образом заработаю несколько очков, я вернусь и посмотрю, смогу ли я это исправить. - person jjj; 05.04.2017
comment
@ Джимми: все в порядке, не беспокойся. - person Rudy Velthuis; 05.04.2017