«Добавить, просто добавить» - это правильное описание, но оно не учитывает прагматически важное условие завершения.(Это также не делает явным тот факт, что числа должны сначала быть выровнены в их осях радиуса, вероятно, потому что авторы оригинальной статьи чувствовали, что эта процедура должна быть неявной в "просто добавить".)
цифры, предшествующие кавычке, следует считать бесконечно повторяющимися влево.Чтобы сложить два числа, мы просто работаем справа налево обычным способом.
Если бы мы сделали это наивно, алгоритм никогда бы не завершился, поскольку неявное представление бесконечно.Но его выход должен в конечном итоге начать циклично работать, потому что это фактически конечный автомат.То есть, как только мы окажемся в левой части кавычки, состояние алгоритма сумм полностью определяется:
- индексом в первом добавлении;
- индекс во втором добавлении;
- и перенос (0 или 1).
Число возможных состояний не более чем в два раза больше произведения двух длин цикла (точнее, это вдвое меньше наименьшего общего кратного длины цикла).Поскольку существует конечное число состояний, некоторое состояние должно повторяться, и это означает, что остальная часть последовательности является циклической.
Вы можете использовать что-то вроде алгоритма черепаха и заяц , чтобы найтиповторное состояние с O (1) дополнительной памятью.Однако, это не находит самое короткое представление.Как только вы найдете циклический префикс, вы должны затем нормализовать число, сместив этот цикл вправо, насколько это возможно.(Вы можете сдвинуть цикл вправо, если первая цифра совпадает с цифрой после кавычки; если это так, опустите первую цифру, сдвиньте кавычку на одну позицию вправо и повторяйте, пока цифры не станут разными.)