1

Пусть есть числа n и m. Необходимо найти такое наименьшее k, что k > n и k % m == 0.
Есть эффективное решение для m == 2**p: k = (n + m) & ~(m-1)
Какое есть эффективное решение для других m? На ум приходит только: k = n - (n % m) + m и k = m * ((n // m) + 1). Но мне оба эти варианта не нравятся, думаю, что можно это реализовать лучше.

8
  • Аналог второго варианта k = ((n + m) // m) * m. Чем же они все плохи?
    – MBo
    13 фев 2019 в 17:31
  • @MBo Мне они не нравятся операциями деления и умножения. Я догадываюсь, что первый вариант эффективнее второго и эффективнее нельзя. но, может быть, умные люди что-то подскажут. 13 фев 2019 в 17:34
  • 2
    Я бы еще понял, если бы это казалось неэффективным где-нибудь в ассемблере... Но в Python? Что вы сэкономите на этих спичках?
    – Harry
    13 фев 2019 в 17:37
  • 1
    Опять же - вы уже твердо знаете (выполнив замеры), что именно эта часть является узким местом вашей программы?
    – Harry
    13 фев 2019 в 18:02
  • 2
    Тогда - раз практика не волнует - поиск в таблице :) А реально - ну нет другого варианта в общем случае... Я прикинул - если числа уже в регистрах, то 4 команд с головой... Да, div и mul, но это очень быстро :)
    – Harry
    13 фев 2019 в 18:43

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.