我怎样才能知道存储1到2^100之间的每一个数字需要多少存储空间?

Question

当涉及到在代码中处理大量数字时，我完全是初学者，我知道这绝对是错误的方法，但这就是我开始的方法。

import tqdm
try:
total = 0
for num in tqdm.tqdm(range(2**100), total=2**100):
total += len(bin(num)) - 2
finally:
with open('results.txt', 'w') as file:
file.write(f'{total=}')

我得到的结果是:

0%|                  | 87580807/1267650600228229401496703205376 [00:39<159887459362604133471:34:24, 2202331.37it/s]

显然这种方法会占用太长的时间。我知道我可以试着把它做成多核的，但我不认为这会对速度有太大的影响。

我在这里有什么选择?

使用另一种语言(如C)会显著提高速度，从而只需要几天或几个小时而不是几个世纪吗?我可以使用其他方法/算法吗?

Answer 1

好吧，我明白了。我用了@jasonharper的方法。

所以代码如下:

total = 0
for power in range(1, 101):
total += ((int('1' * power, base=2) - int('1' + '0' * (power - 1), base=2)) + 1) * power

total等于125497409422594710748173617332225，表示存储1到2^100之间的每个数字所需的字节数。

在某些情况下，需要≈425414947195.2363倍的地球总存储容量来存储1到2^100之间的所有数字。

参考:https://www.zdnet.com/article/what-is-the-worlds-data-storage-capacity/

Answer 2

有趣的问题，但并不是所有的问题都应该用蛮力来解决，这就是算法的一部分。看看你的问题，似乎你想要计算所需的0比特数，直到一些n。现在如果我们仔细看

number of bits    total number of numbers we can represent
1                  2**1 = 2
2                  2**2 = 4
3                  2**3 = 8
4                  2**4 = 16
5                  2**5 = 32
...

所以和就像

1*2 + 2*2 + 3*2^2 + 4*2^3 + ...
= 1 + 1*2^0 + 2*2^1 + 3*2^2 + 4*2^3 + ...
= 1 + sum(k*2^(k-1)) with n from 1 to number of bits
= 1 + (k*2^k - 2^k +1)
= k*2^k - 2^k + 2

可见这是一个几何级数。使用上面的求和方法，可以确定公式

import math
def log2(x):
return math.log(x) / math.log(2)
def count_the_total_number_of_bits_till(n):
neares_2_to_the_power = math.floor(log2(n))
actual_number_of_bits_required = math.ceil(log2(n))

sum_1 = ((neares_2_to_the_power * (2**neares_2_to_the_power)) - (2**neares_2_to_the_power) + 2)
extra_sum = ((n - 2**neares_2_to_the_power) * (actual_number_of_bits_required))

return sum_1 + extra_sum
count_the_total_number_of_bits_till(2**10)

你在做什么

sum_ = 0
for i in range(2**10): 
#equivalent to 
# count_the_total_number_of_bits_till(2**10)
sum_ += len(bin(i)[2:])
print(sum_)