Блог пользователя yeputons

Быстрое деление длинных чисел - как?
Автор yeputons, 13 лет назад, По-русски
Доброе утро.
Кто-нибудь знает алгоритм деления длинных чисел быстрее, чем за квадрат? Слышал, что это можно сделать при помощи преобразования Фурье (умножать им уже умею)
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а умножать как?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    Представим число как многочлен вида a0 + a1· x1 + a2· x2 + ..., где ai - числа, а x = 10. Получаем, что надо перемножить два многочлена. Это можно сделать так: оба преобазовываем при помощи БПФ, перемножаем значения, обратное преобразование.
    Можно посмотреть на e-maxx.ru
    → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Как вариант вначале посчитать 1 / B, а далее A * (1 / B) за nlogn, но посчитать 1 / B быстрее чем за квадрат я лично не находил, возможно ты найдёшь ;O)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
a/b=c, тогда можно перебирать бинпоиском c и проверять чтобы b*c=a. Должно быть довольно быстро, если умножать за n log n. 
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    Двоичный поиск среди десятичных чисел длины N - это N*Log2(10). Так что тогда сложность выходит даже больше квадрата.
    Возможно, тут можно вместо двоичного поиска, как и в извлечении корня, применить Ньютона, к примеру, чтобы найти 1/А. Кажется, Антон Лунёв рассказывал что-то подобное в Харькове...или даже именно это. Правда там 1/А находилось просто с определенной точностью, но если найти с точностью до N знаков, то целая часть от деления должна совпадать с точностью до +-1. Сложность метода емнип была Nlog^2N.
    UPD: Или это был день Дмитрия Жукова..? В любом случае, если интерестно, могу поискать и скинуть в личку потом или выложить куда-то.
    → Ответить
  • 12 лет назад, # ^ |
      Проголосовать: нравится -19 Проголосовать: не нравится

    Ох уж эта любовь везде пропихнуть бинпоиск, хеши или внезапную эвристику..

    → Ответить
    • 12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Ты хотя бы это пропихать научился бы :о

      problems?

      → Ответить
      • 12 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

        Больше никогда не буду брюзжать на тему идеального кода. Больше никогда не буду отвечать на провокационные комментарии или вступать в бесполезную полемику.

        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Насколько я знаю, делить можно просто с помощью FFT. Преобразовали, поделили, преобразовали назад. Однако это не будет работать, если числа делятся с остатком.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ага, угу. Я тоже так думал :) Пусть даже числа делятся нацело.
    А чему равно или ?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня есть большое ощущение, что такого просто не должно произойти. Потому что числа это тоже самое что многочлены, а А значит там где существует одно, существует и другое. А в твоем случае второе не очень существует. А оно первое вроде как существует всегда.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну да. Второе, действительно, не существует, даже понятно почему. А вот с первым проблемы - надо восстановить. Причём контрпример очень простой:
        8 + 8x и 4 + 4x. Делится? Делится. А значения в точке x =  - 1 - нулевые.
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если числа делятся, то скорее всего проще (и быстрее?) будет взять по скольким-то простым модулям, поделить по этим модулям, а потом применить КТО.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Делить с помощью КТО - тот же квадрат (может, константа и получится меньше, но большие числа так всё равно не поделить).
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Например 21 на 7 по основанию 10 так не поделятся.  Получится многочлен 2/7*x+1/7 и что с ним делать непонятно
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, а никто не в курсе, как реализованы деление и умножение BigInteger'ов в Java?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Гугление даёт много чего интересного, большая часть методов считает 1/A с какой-то точностью, а потом умножает на B. Статья в вики вполне содержательная, сразу виден "халявный" метод с помощью Ньютона - делать итерации вида xn + 1 = xn(2 - Axn). Кроме того, в гуглящихся статьях можно найти алгоритмы, которые асимптотически не медленнее, чем умножение.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Действительно.
    Спасибо, еще не научился, что на английском можно искать статьи и по алгоритмам :)
    → Ответить