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

...которые не влезут "совсем никуда", ни в какие типы данных, например, 20+21+...+2100. При этом, хотелось бы точно, а не с точностью до порядка.

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

Искомый предел суммирования (верхнюю степень двойки) обозначим m, предельный размер массива n, грубо оценить его можно, например, как n = m/2, на самом деле, с ростом степени числа нужно меньше знаков. Да и если переборщим с размером массива, не страшно, просто в числе останутся лидирующие нули.

В листинге ниже проверяется "число зёрен на шахматной доске", вроде, совпало.

#include <stdio.h>

void udvoyalka (int n, int *a) {
 for (int i=n-1; i>-1; i--) {
  a[i]*=2;
  if (a[i]>9) a[i+1]+=a[i]/10;
  a[i]%=10;
 }
}

void main () {
 const int n = 19, //Размер буфера под запись числа
	   m = 64; //Степень двойки, до которой вычисляем (не включая)
 int s[n+1],i;
 for (i=0; i<=n; i++) s[i]=0;
 s[0]=1;
 for (i=1; i<=m; i++) udvoyalka (n,s);
 s[0]--;
 for (i=n; i>-1; i--) printf ("%d",s[i]);
 getchar ();
}

Фактически, здесь реализовано умножение в столбик на 2. Число при этом представлено как массив, в котором младшие разряды числа начинаются с 0-го элемента. То есть, считается сумма ряда 20+21+...+263, представленного формулой

Вычислить сумму степеней двойки, например, до 2¹¹⁰⁰ включительно, ни один пакет уже не может, предел точности для типа double ~ 10³⁰⁸, но мы, подставив в программу n=332, m=1101, легко получим ответ:

02716597058098771698554702856718533557206987693863489099497039339455626185508483
69744107841664151211845971565259076947669500774510864698599423110966856012574437
71526998812780663565728288329361461533674321052446353025596871544259913106710572
06440616076155151946464039797018976800813823224616829575087436731693493029789758
1105488330751

(это одно число, переносы строк, чтоб не "рвало макет").

(а сама запись, чтоб проверить rss, что-то напортачил в шаблоне спьяну)

11.10.2014, 21:55 [12804 просмотра]