Сколько стоит хранилище для суммирования от 1 до 4 миллиардов

Question

Вдохновленный этим вопросом ( Найдите целое число среди четырех миллиардов заданных ).

Сколько места потребуется для хранения целого числа, которое было суммой чисел 1до 4 миллиардов?

Например, 1 + 2 + 3 + 4 + 5 = 15. Суммирование от 1 до 1 миллиона = 500 000 500 000.

Здесь - это алгоритм, который может помочь

Answer 1

In [12]: import math

In [13]: n=4000000000

In [15]: sumn = n*(n+1)/2

In [16]: sumn
Out[16]: 8000000002000000000L

In [24]: math.log(sumn)/math.log(2)
Out[24]: 62.794705708333197

Ответ: 63 бита.

Answer 2

Функция, на которую вы ссылаетесь, чтобы описать, как найти n'th Треугольное число , которое определяется как сумма n натуральных чисел от 1 до n.

Подстановка 4 миллиардов n в функцию дает 8000000002000000000.

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

ceil (log (8000000002000000000) / log (2)) = 63

Итак, требуется 63 бита.

Answer 3

Один бит достаточно, если вы выберете подходящую кодировку для целых чисел.

Вам нужно больше, чем n битов, если есть более 2 ^ n возможных значений, которые вы потенциально можете хранить. Здесь есть только одно значение, которое вам необходимо сохранить.