Ограничение этой программы для определения суммы обратных целых чисел, не содержащих нуля

При правильном подходе это не так уж и сложно.

Предположим, например, что вы хотите найти сумму обратных чисел всех целых чисел, начинающихся (то есть крайних левых цифр) со 123 и заканчивающихся k ненулевыми цифрами. Очевидно, что таких целых чисел 9 ^k, и величина, обратная каждому из этих чисел, находится в диапазоне 1 / (124 * 10 ^k) .. 1 / (123 * 10 < sup> k). Следовательно, сумма обратных значений всех этих целых чисел ограничена (9/10) ^k / 124 и (9/10) ^k / 123.

Чтобы найти границы для суммы всех обратных чисел, начиная с 123, необходимо сложить указанные выше границы для каждого k> = 0. Это геометрическая серия, поэтому можно вывести, что сумма обратных целых чисел, начинающихся с 123, ограничена 10 * (9/10) ^k / 124 и 10 * (9/10) < sup> k / 123.

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

def approx(t,k):
    """Returns a lower bound and an upper bound on the sum of reciprocals of
       positive integers starting with t not containing 0 in its decimal
       representation.
       k is the recursion depth of the search, i.e. we append k more digits
       to t, before approximating the sum. A larger k gives more accurate
       results, but takes longer."""
    if k == 0:
      return 10.0/(t+1), 10.0/t
    else:
        if t > 0:
            low, up = 1.0/t, 1.0/t
        else:
            low, up = 0, 0
        for i in range(10*t+1, 10*t+10):
            l,u = approx(i, k-1)
            low += l
            up += u
    return low, up

Например, вызов приблизительно (0, 8) дает нижнюю и верхнюю границу: 23.103447707 ... и 23.103448107 ...., что близко к утверждению 23.10345, данному OP.

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

Для всех значений current, превышающих некоторый порог N, 1.0/(double)current будет достаточно малым, чтобы total не увеличился в результате добавления 1.0/(double)current. Таким образом, критерий прекращения должен быть примерно таким:

 while(total != total + (1.0/(double)current))

вместо тестирования на соответствие пределу, который известен a priori. Ваш цикл остановится, когда current достигнет этого особого значения N.

Я подозреваю, что преобразование в строку с последующей проверкой символа «0» - это этап, который занимает слишком много времени. Если вы хотите избежать всех нулей, может помочь увеличить current таким образом:

(Отредактировано - спасибо Аарону МакСмуту)

current++;  
for( int i = 10000000; i >= 10; i = i / 10 )  
{
    if ( current % i ) == 0
    {
         current = current + ( i / 10 );
    }
}

Это не проверено, но концепция должна быть ясной: всякий раз, когда вы попадаете в степень, кратную десяти (например, 300 или 20000), вы добавляете следующую меньшую степень 10 (в наших примерах 10 + 1 и 1000 + 100 + 10 + 1 соответственно) до тех пор, пока в вашем номере не останется нулей.

Измените ваш while цикл соответствующим образом и посмотрите, не помогает ли это производительности до такой степени, когда ваша проблема становится управляемой.

О, и вы можете также немного ограничить вывод System.out. Будет ли хватить каждой десятой, сотой или 10000-й итерации?

Измените второе: Я подозреваю, что после некоторого сна мой ответ может быть немного близоруким (вините в этом поздний час, если хотите). Я просто надеялся, что, ох, миллион итераций current приведут вас к решению, и оставил все как есть, вместо того, чтобы вычислять варианты исправлений с использованием log( current ) и т. Д.

Поразмыслив, я вижу две проблемы во всей этой проблеме. Во-первых, ваше целевое число 23,10345 - на мой вкус очень мало. В конце концов, вы добавляете тысячи элементов, таких как «1/17», «1/11111» и так далее, с бесконечным десятичным представлением, и очень маловероятно, что они в сумме дадут ровно 23,10345. Если так говорит какой-нибудь специалист по вычислительной математике, хорошо, но тогда мне хотелось бы увидеть алгоритм, по которому они пришли к такому выводу.

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

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

Измените третье. Из любопытства я написал это на C ++, чтобы проверить свои теории. Он работает 6 минут и составляет около 14,5 (примерно 550 миллионов итераций). Посмотрим.

Текущая версия

double total = 0;
long long current = 0, currPowerCeiling = 10, iteration = 0;
while( total < 23.01245 )
{
    current++;
    iteration++;
    if( current >= currPowerCeiling )
        currPowerCeiling *= 10;

    for( long long power = currPowerCeiling; power >= 10; power = power / 10 )  
    {
        if( ( current % power ) == 0 )
        {
            current = current + ( power / 10 );
        }
    }
    total += ( 1.0 / current );

    if( ! ( iteration % 1000000 ) )
        std::cout << iteration / 1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl;
}
std::cout << current << "\t" << total << std::endl;

Вычисление currPowerCeiling (или как его можно назвать) вручную сохраняет некоторые log10 и pow вычисления на каждой итерации. Любая мелочь помогает - но все равно занимает вечность ...

Измените четвертое: Статус составляет около 66 000 миллионов итераций, общее количество - до 16 2583, время выполнения - около 13 часов. Не очень хорошо, Бобби С. - Я предлагаю более математический подход.

Как насчет сохранения текущего числа в виде массива байтов, где каждый элемент массива представляет собой цифру 0-9? Таким образом, вы можете очень быстро обнаружить нули (сравнивая байты, используя == вместо String.contains).

Обратной стороной будет то, что вам нужно будет реализовать инкремент самостоятельно вместо использования ++. Вам также необходимо разработать способ пометки «несуществующих» цифр, чтобы вы не определяли их как нули. Сохранение -1 для несуществующих цифр звучит как разумное решение.

Для 32-битного целого числа со знаком эта программа никогда не остановится. Фактически он будет сходиться к -2097156. Поскольку максимальное количество гармоник (сумма обратных величин от 1 до N) 32-битного целого числа со знаком равно ~14.66, этот цикл никогда не завершится, даже если ток будет меняться от 2^31 - 1 до -2^31. Поскольку величина, обратная наибольшему отрицательному 32-битному целому числу ~ -4.6566e-10, каждый раз, когда ток возвращается к 0, сумма будет отрицательной. Учитывая, что наибольшее число, представимое double, такое, что number + + 1/2^31 == number равно _8 _ / _ 9_, вы получите примерно -2097156 в качестве сходящегося значения.

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

Однако вы также тратите много времени на определение того, есть ли в числе ноль. Вы можете перевернуть этот тест, чтобы сгенерировать диапазоны целых чисел, так что в этом диапазоне вы гарантированно не получите целое число с нулевой цифрой. Это действительно просто сделать постепенно (в C ++, но достаточно тривиально, чтобы преобразовать в Java):

class c_advance_to_next_non_zero_decimal
{
public:
    c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0)
    {
        std::fill_n(digits, digit_count, 0);

        return;
    }

    int advance_to_next_non_zero_decimal()
    {
        assert((next % 10) == 0);

        int offset= 1;
        digits[0]+= 1;

        for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10)
        {
            if (digits[digit_index]==0)
            {
                digits[digit_index]= 1;
                offset+= digit_value;
            }
        }

        next+= offset;

        return next;
    }

    int advance_to_next_zero_decimal()
    {
        assert((next % 10)!=0);
        assert(digits[0]==(next % 10));

        int offset= 10 - digits[0];
        digits[0]+= offset;
        assert(digits[0]==10);

        // propagate carries forward
        for (int digit_index= 0; digits[digit_index]==10 && digit_index<digit_count; ++digit_index)
        {
            digits[digit_index]= 0;
            digits[digit_index + 1]+= 1;

            max_set_digit_index= max(digit_index + 1, max_set_digit_index);
        }

        next+= offset;
        return next;
    }

private:
    int next;

    static const size_t digit_count= 10; // log10(2**31)

    int max_set_digit_index;

    int digits[digit_count];
};

Приведенный выше код выполняет итерацию по каждому диапазону чисел, так что диапазон содержит только числа без нулей. Он работает, определяя, как перейти от N000 ... к N111 ... и от N111 ... к (N + 1) 000 ..., перенося (N + 1) в 1 (0) 000 ... если необходимо.

На моем ноутбуке я могу сгенерировать гармоническое число 2 ^ 31-1 за 8,73226 секунд.

public class SumOfReciprocalWithoutZero {
public static void main(String[] args) {

    int maxSize=Integer.MAX_VALUE/10;
    long time=-System.currentTimeMillis();
    BitSet b=new BitSet(maxSize);
    setNumbersWithZeros(10,maxSize,b);

    double sum=0.0;
    for(int i=1;i<maxSize;i++)
    {
        if(!b.get(i))
        {
            sum+=1.0d/(double)i;
        }
    }
    time+=System.currentTimeMillis();
    System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms");


}

 static void setNumbersWithZeros(int srt,int end,BitSet b)
 {
        for(int j=srt;j<end;j*=10)
        {
            for(int i=1;i<=10;i++)
        {
            int num=j*i;
            b.set(num);
        }
            if(j>=100)
            setInbetween(j, b);
        }
 }

 static void setInbetween(int strt,BitSet b)
 {

     int bitToSet;
     bitToSet=strt;
     for(int i=1;i<=10;i++)
     {
      int nxtInt=-1;

     while((nxtInt=b.nextSetBit(nxtInt+1))!=strt)
     {
         b.set(bitToSet+nxtInt);
     }
     nxtInt=-1;
     int lim=strt/10;
     while((nxtInt=b.nextClearBit(nxtInt+1))<lim)
     {
         b.set(bitToSet+nxtInt);
     }

     bitToSet=strt*i;

     }
 }


}

Это реализация с использованием BitSet. Я вычислил сумму обратных значений для всех целых чисел в диапазоне (1-Integer.MAX_VALUE/10). Сумма составляет 13.722766931560747. Это максимум, который я мог вычислить с помощью BitSet, поскольку максимальный диапазон для BitSet равен Integer.MAX_VALUE. Мне нужно разделить его на 10 и ограничить диапазон, чтобы избежать переполнения. Но есть значительное улучшение скорости. Я просто публикую этот код на случай, если он может дать вам новую идею для улучшения вашего кода. (Увеличьте объем памяти, используя аргумент VM -Xmx[Size>350]m )

Вывод:

Total: 13.722766931560747
TimeTaken : 60382 ms

ОБНОВЛЕНИЕ:

Перенос на Java предыдущего удаленного ответа:

     public static void main(String[] args) {
        long current =11;
        double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9;
        long i=0;
        while(true)
        {
            current=next_current(current);
            if(i%10000!=0)
                System.out.println(i+" "+current+" "+tot);
            for(int j=0;j<9;j++)
            {
                tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) +
                          1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8));

                current += 10;
            }
            i++;
        }

    }

    static long next_current(long n){

    long m=(long)Math.pow(10,(int)Math.log10(n));
    boolean found_zero=false;
    while(m>=1)
    {
        if(found_zero)
            n+=m;
        else if((n/m)%10==0)
        {
            n=n-(n%m)+m;
           found_zero=true;
        }

     m=m/10;
    }
    return n;
    }