Как реализовать умножение на целое число с большим целым числом в ocaml без библиотечных функций?

Question

В настоящее время я пытаюсь реализовать умножение на целое число с большим целым числом в Ocaml без библиотечных функций.

Вот что у меня есть:

let rec mulByDigit i l = 
  match l with
    [] -> []
  | h::t -> 
      match t with
        [] -> [(h*i) mod 10]
      | x::y -> 
          match y with
            [] -> [x*i/10+(h*i) mod 10]@mulByDigit i t
          | a::b -> [(x*i/10+(h*i)mod 10+(a*i/10+(x*i) 
                             mod 10)/10) mod 10]@mulByDigit i t

, что для i = 9 и l = [9; 9; 9; 9] дает мне [9; 9; 9; 1], когда требуется [8; 9; 9; 9; 1]

Насколько я понимаю, алгоритм для этого состоит в том, чтобы взять информацию из последней цифры * i, текущей цифры * i и следующей цифры * i, чтобы построить текущую цифру для списка ответов. Однако есть 2 случая, когда это не так. Для первой цифры и последней цифры в списке ответов последняя цифра получает информацию из текущей цифры * i и предыдущей цифры * i из списка ввода, а первая цифра получает информацию из текущей цифры * i и следующей цифры * я из списка ввода. Я могу позаботиться о специальном случае последней цифры из-за соответствия шаблона с [] в самом конце, но я не могу понять, как выполнить специальный случай для первой цифры, так как я не вижу условий, которые я мог бы вставить оператор if then должен выполняться только при первоначальном вызове этой функции.

Любая помощь будет оценена.

Answer 1

Ну, это тоже звучит как домашнее задание.Вот пара наблюдений.

Вы можете получить более красивый код, если вы представляете свои числа цифрой в начале списка, а не в хвосте.Обычно вы хотите обрабатывать вещи, начиная с конца единиц, и это имеет математическую правильность (множитель на n-й позиции в списке равен 10 ** n).Но, возможно, вы не можете контролировать свое представление.

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

Вы определенно не хотите думать о функциях, которые делаютчто-то другое в первый раз, когда их называют!Это не функция, это обязательное программирование.

С уважением,

Answer 2

Я бы рассмотрел это по-другому. Например, вы могли бы написать одну функцию, которая просто умножает, не беспокоясь о переносе, а затем вторую функцию, которая обрабатывает перенос.

Как предлагает Джеффри, вы также можете поменять цифры, как правило, или просто по мере необходимости. Хотя вам, по-видимому, запрещено использовать функцию List.reverse, вы можете реализовать ее самостоятельно в одной строке кода.

О, и ради эффективности и / или хороших привычек вам, вероятно, следует переписать части, которые говорят [one value]@list, чтобы вместо них сказать (one value)::list. Они будут делать то же самое, и второй будет быстрее первого (если компилятор не достаточно умен, чтобы выполнить эту замену для вас, какой она может быть, и в этом случае это будет та же скорость).