О признаках делимости

[janatem]

Можно заметить, что признаки делимости на 3, 7, 11 и др. - это обман трудящихся, поскольку они не дают асимптотически значимого выигрыша по сравнению с прямолинейным делением. Например, признак делимости на 3 требует сложить цифры числа по модулю 3, что дает ~N операций, где N - количество цифр числа, в то время как деление уголком дает те же O(N

Comments

[a_shen]

Естественно - в остальных случаях нужно прочесть все цифры, так как любая из них может повлиять на делимость

[janatem]

Действительно, совсем тривиально оказалось.

[dimmik]

А еще же есть калькулятор. С его помощью определение делится ли число на x осуществляется за одно действие.

[janatem]

Разумеется, не за одно действие. (Хотя, смотря что подразумевать под действием.) Цифр в числе может быть, например, 10000, и я не видел процессоров соответствующей разрядности.

[dimmik]

Это я к тому что признак делимости не для понижения сложности алгоритма нужен, а для удобства человека

[dimmik]

Это я к тому что признак делимости не для понижения сложности алгоритма нужен, а для удобства человека.
С точки зрения человека самое простое - поделить на калькуляторе (http : / / c omptune.com/calc.php?methos=GET&base1=10&base2=10&S1=55075077123297422842904086506475615025267365694781%0D%0A78998719567043914306660101081408856857010041604145%0D%0A02772255599786794789066346386820234085949632247594%0D%0A99366326138693663422188337753876323573533042773799%0D%0A258308009751&S2=35&func=bcdiv&base3=10&places=500 например)
Дальше - разумные признаки делимости (2, 3, 5, 6, 7, 9, 11 - те что не требуют "сложных" действий, типа "утроить количество десятков и прибавить единицу").
Потом уже поделить в столбик.
1000-значное число в столбик делить то еще удовольствие. А вот сложить цифры и понять делится ли на три - уже за пару часов можно. Даже меньше.

[quicknose]

А операция сложения считается заведомо такой же простой как и операция деления?

[janatem]

Разумеется, в общем случае нет. Но конкретно в признаке деления на три элементарной операцией является (а) сложение двух цифр по модулю три (традиционная схема), либо (б) вычисление остатка от деления на 3 двузначного числа (деление уголком без записи частного). Для других признаков делимости могут быть аналогичные упрощения при делении уголком.

[technocrator]

А ведь отличная задачка! Можно утянуть идею для использования для практики или экзамена по теории сложности?

Кстати, нет ли желания всё-таки вернуться в ЖЖ?)

[janatem]

Утянуть, разумеется, можно всё, что лежит в публичном доступе. Только я не вижу особой ценности в моем замечании, поскольку оно оказалось тривиальным (см. первый же комментарий).

Вернуться в ЖЖ есть повод: меня в фейсбуке забанили, и, похоже, надолго. ;)

[technocrator]

в методическом плане - очень хорошая задачка для студентов.
Потихоньку собираю такие вещички, для ответа на которые надо понимать базовые вещи, и чтоб ответ не гуглился :)

фейсбук уроды, конечно. Главное, свежие аккаунты они тоже блочат ни за что через какое-то время...