Как умножить два больших больших числа

Ответ 1

Я хотел бы объединить наблюдение Амнона о множительной способности 2 с одной из моих по поводу подписок.

Списки заканчиваются на 0. Мы можем разбить проблему на поиск самого большого продукта в каждом под-списке, а затем максимум этого. (Другие упомянули об этом).

Это моя 3-я ревизия этой записи. Но 3 очарование...

Подход

Учитывая список не-0 чисел (это то, о чем много размышляло), есть 3 поддиапазона:

• Список содержит четное число отрицательных чисел (возможно, 0). Это тривиальный случай, оптимальный результат - произведение всех чисел, гарантированное положительное.

• В списке содержится нечетное число отрицательных чисел, поэтому произведение всех чисел будет отрицательным. Чтобы изменить знак, необходимо пожертвовать подпоследовательность, содержащую отрицательное число. Два поддиапазона:

  а. жертвовать числами слева до и включая самый левый отрицательный; или

  б. жертвуйте номерами справа и справа от самого отрицательного.

  В любом случае верните произведение остальных чисел. Пожертвовав ровно одно отрицательное число, результат наверняка будет положительным. Выберите победителя (a) и (b).

Реализация

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

Выполнение математики в longs только удвоило бы возможный диапазон. Преобразование в log2 упрощает арифметику с большими продуктами. Это предотвращает отказ программы на больших последовательностях больших чисел. В качестве альтернативы можно было бы выполнить всю математику в Bignums, но это, вероятно, будет работать плохо.

Наконец, конечный результат, все еще номер журнала2, должен быть преобразован в печатную форму. Там вам пригодится Bignum. Там new BigInteger("2").pow(log);, который поднимет 2 на мощность log.

Сложность

Этот алгоритм работает последовательно через под-списки, обрабатывая только один раз. Внутри каждого под-списка существует раздражающая работа по преобразованию ввода в log2 и результат обратно, но усилие является линейным по размеру списка. В худшем случае сумма большей части списка вычисляется дважды, но также и линейная сложность.

Ответ 2

В моем первом ответе я обратился к проблеме ОП в "умножении двух больших больших чисел". Как оказалось, это желание является лишь малой частью гораздо большей проблемы, к которой я сейчас обращусь:

"Я до сих пор не дошел до финального скелета моего алгоритма, мне интересно, можете ли вы помочь мне в этом".

(см. вопрос для описания проблемы)

Все, что я собираюсь сделать, это объяснить подход, предложенный Амноном чуть более подробно, так что все кредиты должны пойти ему.

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

• Вычислить произведение каждого непрерывного подсписок.
• Верните самый большой из всех этих продуктов.

Вы можете представить подсписку по индексу start и end. Для start=0 существует n-1 возможных значений для end, а именно 0..n-1. Это генерирует все подсписки, начинающиеся с индекса 0. На следующей итерации вы увеличиваете start на 1 и повторяете процесс (на этот раз для end есть n-2 возможных значений). Таким образом, вы создаете все возможные подсписки.

Теперь, для каждого из этих подписок, вам нужно вычислить произведение его элементов - это метод computeProduct(List wholeList, int startIndex, int endIndex). Вы можете использовать встроенный класс BigInteger (который должен иметь возможность обрабатывать ввод, предоставленный вашим назначением), чтобы избавить вас от дальнейших проблем или попытаться реализовать более эффективный способ умножения, как описано другими. (Я бы начал с более простого подхода, так как было легче увидеть, правильно ли работает ваш алгоритм, а затем попытаться его оптимизировать.)

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

Если вам все еще трудно установить соединения между двумя шагами, сообщите нам, но, пожалуйста, также предоставьте нам проект вашего кода, когда вы работаете над проблемой, чтобы мы не постепенно увеличивали решение, и вы копируете и вставляете его.

изменить: Скелет алгоритма

public BigInteger listingSublist(BigInteger[] biArray)
{       
    int start = 0;
    int end = biArray.length-1;
    BigInteger maximum;

    for (int i = start; i <= end; i++)
    {
        for (int j = i; j <= end; j++)
        {
            //insert logic to determine the maximum product.
            computeProduct(biArray, i, j);
        }
    }

    return maximum;                
}

public BigInteger computeProduct(BigInteger[] wholeList, int startIndex, 
                                                         int endIndex)
{
    //insert logic here to return
    //wholeList[startIndex].multiply(wholeList[startIndex+1]).mul...(
    //    wholeList[endIndex]);       
}

Ответ 3

Так как k <= 30, любое целое число я = 2 ^k будет вписываться в Java int. Однако произведение таких двух целых чисел может не обязательно вписываться в Java int, так как 2 ^k * 2 ^k= 2 ^{2 * k} <= 2 ⁶⁰ которые заполняются в Java long. Это должно ответить на ваш вопрос относительно "(умножения) двух чисел...".

В случае, если вы захотите умножить больше двух чисел, что подразумевается в вашем задании, в котором говорится: "... самый большой продукт CONTINUOUS SUBLIST..." (длина подписок может быть > 2), посмотрите в классе Java BigInteger.

Ответ 4

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

Конечно, для сохранения результата вам может понадобиться BigInteger, если у вас заканчивается бит. Или в зависимости от того, как должен выглядеть вывод, просто скажите (+/-) 2 ^ N, где N - сумма показателей.

Разбор ввода может быть вопросом переключения, так как у вас есть только 30 номеров. Плюс негативы.

Это скучная часть. Интересная часть заключается в том, как вы получаете подсписку, которая производит наибольшее число. Вы можете принять глупый подход, проверив каждый вариант, но это будет алгоритм O (N ^ 2) в худшем случае (IIRC). Что действительно не очень хорошо для более длинных входов.

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

Ну, я не знаю, работает ли этот alogrithm, но если он (или что-то подобное) делает, его алгоритм O (N), что означает большую производительность. Попробуем!: -)

Ответ 5

EDIT: я скорректировал схему алгоритма, чтобы соответствовать фактическому псевдокоду, и поместил анализ сложности непосредственно в ответ:

Схема алгоритма

Перейдите последовательно по последовательности и сохраните значение и первый/последний индекс продукта (положительный) с момента последнего 0. Сделайте то же самое для другого продукта (отрицательного), который состоит только из чисел, поскольку первое изменение знака последовательности, Если вы нажмете элемент отрицательной последовательности, поменяйте два продукта (положительные и отрицательные) вместе с ассоциативными начальными индексами. Всякий раз, когда позитивный продукт попадает в новый максимум, сохраняйте его и связанные с ним начальные и конечные индексы. После прохождения всей последовательности результат сохраняется в максимальных переменных.

Чтобы избежать вычисления переполнения в двоичных логарифмах и дополнительного знака.

Псевдокод

maxProduct = 0
maxProductStartIndex = -1
maxProductEndIndex = -1
sequence.push_front( 0 ) // reuses variable intitialization of the case n == 0

for every index of sequence
   n = sequence[index]
   if n == 0
       posProduct = 0
       negProduct = 0
       posProductStartIndex = index+1
       negProductStartIndex = -1
   else
       if n < 0
           swap( posProduct, negProduct )
           swap( posProductStartIndex, negProductStartIndex )
           if -1 == posProductStartIndex // start second sequence on sign change
               posProductStartIndex = index
           end if
           n = -n;
       end if
       logN = log2(n) // as indicated all arithmetic is done on the logarithms
       posProduct += logN
       if -1 < negProductStartIndex // start the second product as soon as the sign changes first
          negProduct += logN
       end if
       if maxProduct < posProduct // update current best solution
          maxProduct = posProduct
          maxProductStartIndex = posProductStartIndex
          maxProductEndIndex = index
       end if
   end if
end for

// output solution

print "The maximum product is " 2^maxProduct "."
print "It is reached by multiplying the numbers from sequence index " 
print maxProductStartIndex " to sequence index " maxProductEndIndex

Сложность

Алгоритм использует один цикл над последовательностью, поэтому его O (n) умножает сложность тела цикла. Наиболее сложной операцией тела является log2. Ergo его O (n) умножает сложность log2. Лог2 некоторого ограниченного размера равен O (1), поэтому полученная сложность O (n) aka linear.

Ответ 6

Хммм.. поскольку все они имеют силу 2, вы можете просто добавить экспонента вместо умножения чисел (что эквивалентно принятию логарифма продукта). Например, 2 ^ 3 * 2 ^ 7 равно 2 ^ (7 + 3) = 2 ^ 10. Я оставлю обращение к знаку как упражнение для читателя.

Что касается проблемы подвыписки, то существует меньше n ^ 2 пар индексов (начала, конца). Вы можете проверить их все или попробовать динамическое программирование.

Ответ 7

Смотрите этот код. Здесь я реализую точный факториал огромного большого числа. Я просто использую целочисленный массив для создания больших чисел. Загрузите код из Исходный код планеты.