Вычисление больших степеней 2 в десятичной

Итак, это моя проблема:

Я хочу вычислить \ $ 2 ^ n \ $, где \ $ 0 <п & л; 10000 \ $

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

Принцип, который я использую, выглядит следующим образом:

 введите описание изображения здесь>> </a> </p>

<p> Код, который я использую, следующий: </p>

<pre><code>---- +: = 0 = + ----</code></pre></body></html>

11 голосов | спросил Beginner 6 J0000006Europe/Moscow 2018, 01:01:01

1 ответ


25
  

Как я могу сделать этот алгоритм лучше?

Вот как я лучше сделаю ваш алгоритм.

Во-первых: ваш принцип звучит. Вы показываете большое двоичное число в базе 10, воспользовавшись тем, что int уже имеет метод, который отображает 32-битное число в база 10. По существу ваш метод:

  • преобразуем число в базовую 10000, сделав «массивы» массива int от 0 до 9999.
  • Сделайте устройство, которое может удвоить одно из этих номеров.
  • Распечатайте результат после заданного количества удвоений.

Этот метод работает, но ваша реализация может использовать некоторые улучшения. Улучшения, которые я бы сделал, следующие:

  • Иди большой! Почему база 10000? Вы можете сделать базу 100000000 в int без проблем или базы 1000000000000000000 в течение долгого времени. Давайте сделаем это.
  • Вы выделяете огромное количество int. Вероятно, это слишком много или слишком мало для этой проблемы. Не ограничивайте себя. Сделайте решение, которое растет по мере необходимости, а не тот, который имеет произвольный предел. Более того: вы делаете 3750 ints, но вы можете сделать всю проблему всего 167 длин.
  • Отрисуйте свои операции в виде, представляющем значение
  • Реорганизовать каждую часть алгоритма в вспомогательный метод, который хорошо работает.
  • Прекратить использование изменчивого состояния. Это нормально, чтобы записать небольшую память. Сборщик мусора будет иметь дело.
  • Используйте более эффективный алгоритм для вычисления больших мощностей.

Как мы можем применить эти принципы на практике? Попробуем.

Во-первых, я собираюсь создать структуру, которая представляет число, закодированное в базе 1000000000000000000. Его реализация будет списком длин, но это может быть любой тип коллекции. Списки удобны.

(Помимо: Почему struct? Реализация небольшая, это оболочка вокруг одной ссылки. Значение структуры логически является значением . Это immutable , поэтому это хороший кандидат для типа значения. Мы получаем преимущества наличия скрытого интерфейса и реализации, но мы платим только за одну ссылку.)

struct Base1000000000000000000
{
    private List<long> digits;
    private Base1000000000000000000(List<long> digits) {
        this.digits = digits;
    }

Обратите внимание, что пока все закрыто. Я хочу, чтобы у этого был очень закрытый интерфейс. Мы должны начать эту вечеринку, так что давайте представим ее:

  public static readonly Base1000000000000000000 One = 
    new Base1000000000000000000(new List<long> { 1L });

Аналогичным образом можно сделать Zero.

Теперь, как выглядит наш алгоритм отображения? Это однострочный:

public override string ToString() =>
    string.Join("",
        ((IEnumerable<long>)digits)
          .Reverse()
          .Select(d => d.ToString().PadLeft(18, '0')));

Обратите внимание, что мы используем неразрушающий обратный, а не деструктивный реверс в списке.

Ядро алгоритма находится в нашем сумматоре, который принимает число и возвращает его double:

  public Base1000000000000000000 DoubleIt() 
  { 
    // Note, _ separators in constants are new for C# 7.
    const long TheBase = 1_000_000_000_000_000_000;
    var result = new List<long>();
    result.Add(0);
    for (int i = 0; i < this.digits.Count; i += 1)
    {
      // Make sure we have storage.
      if (i == result.Count)
        result.Add(0);
      result[i] += this.digits[i] + this.digits[i];
      // We might have to carry.
      if (result[i] >= TheBase)
      {
        // Again, make sure we have room.
        if (i + 1 == result.Count)
          result.Add(0);
        result[i+1] = result[i] / TheBase;
        result[i] -= TheBase;
      }
    }
    // And we're done.
    return new Base1000000000000000000(result);
  }

Super. Теперь основной алгоритм прост:

Base1000000000000000000 c = Base1000000000000000000.One;
for (int i = 0; i < n; ++i)
  c = c.DoubleIt();
return c.ToString();

Обратите внимание, что когда я извлекаю каждую операцию по своему методу, код становится проще и элегантнее .

Теперь, как вы можете улучшить это дальше?

  • Упражнение : (Легко) Внесите operator+ в этот тип.
  • Упражнение : (Довольно легко) Внесите operator- в этот тип и правильно представляйте отрицательные числа.
  • Упражнение : (Hard) Внесите operator* в этот тип.
  • Упражнение : (Очень сложно) Теперь, когда у вас есть умножение и добавление, вы можете быстрее перейти на 2 n . Предположим, вы хотите сделать 2 384 . Начните с One. Двойной. Теперь у вас есть 2 1 . Умножьте его на себя - соберите его. Теперь у вас есть 2 2 . Квадрат снова, чтобы получить 2 4 . Квадрат снова, чтобы получить 2 8 . И так далее, пока у вас их не будет до 2 256 . Умножьте 2 256 на 2 128 , чтобы получить 2 384 , и все готово. Ваш оригиналалгоритм делает 384 удвоения, но вы можете получить ответ с удвоением и девятью умножениями. Можете ли вы разработать алгоритм оптимальной последовательности умножений и дополнений ?
  • Упражнение (Очень сложно): Внедрить % и / в этом типе.
  • Упражнение (очень сложно): Теперь сделайте это снова и снова без использования встроенного типа для математики . (Для текста используйте string.) Вы используете возможность int или long для представления битового поля, которое может отображаться в базе 10. Что делать, если у вас не было что? Потому что кто-то должен был написать этот код . У человека, написавшего этот код, его нет, потому что он еще не написан. Предположим, что у C # не было целочисленного типа; как бы вы реализовали математику с нуля?
ответил Eric Lippert 6 J0000006Europe/Moscow 2018, 01:34:14

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132