|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Aleksey Malov 2:5052/30.8 20 Sep 2001 01:33:07
To : Denis Petrushenko
Subject : Деление 50-ти значных чисел
--------------------------------------------------------------------------------
DP> Даны два 50-ти значных(или менее значных числа).Известно, что одно
DP> является делителем другого. Hеобходимо разделить их не используя
DP> оператора деления. Результат - целое число(максимум
DP> пятидесятизначное). Вычисление любого результата за 15 или менее
DP> секунд(обязательно).
DP> Может у кого-нибудь есть идеи?(желательно поподробнее)
Переводишь их (делимое и делитель) в двоичный вид (займет около 160 бит).
Затем делить в столбик (используq сложение, вычитание и сдвиг влево(можно
заменить сложением)) 160-битные двоичные числа за 160 циклов, каждый из которых
выполняется на асме на пне за несколько десятков тактов. Потом переводишь
результат обратно в десятичную систему, используя сложения и команды
двоично-десятичной арифметики (тоже 160 циклов, каждый из которых занимает
несколько десятков тактов).
Результат на пне можно получить за несколько десятков тысяч тактов (быстрее, чем
за тысячную долю секунды на Pentium-100). Если интересует конкретно алгоритм
деления двоичных чисел или конкретно алгоритм перевода из дес. в двоичную
систему и обратно, то прошу в нетмейл. Для понимания сути алгоритма надо знать
ассемблер.
Bye, Denis.
WBR, Vivid^Brainwave of the X-Project association.
--- Lara Croft за 4.50 $.
* Origin: http://brainwave.dax.ru (2:5052/30.8)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
