Задача 1.181 / Програмиране++=Алгоритми

agogo 12 Точки

Задача 1.181 / Програмиране++=Алгоритми

Здравейте!

Вместо да ходя на море :) се опитвам да реша следната задача:

1.181: Да се намери минималното n, за което първите девет цифри на числото 2 на степен n са 123454321.

Ето моя код: http://fdos.free.bg/sklad/1_181.c

Ето резултати от изпълнение:

при първи цифри:

123 ( n = 90 ) < 1s
1234 ( n = 1545 ) < 1s
12345 ( n = 34555 ) ~ 2s
123454 ( n = 176109 ) ~ 10s
1234543 ( n = 176109 ) ~ 10s

12345432 - изпълнява се повече от 50 мин и продължава.

Искам да попитам има ли по-рационално решение от това, което използвам като алгоритъм?

И дали сте решавали тази задачи и какъв резултат сте получили

Благодаря, предварително!

Тагове:

19/08/2016 18:31:47 C Programming

Виж всички отговори

MartinBG 4803 Точки

Тази задача не ми излизаше от главата, откакто я видях тук, а след като си купих и книгата, намирането на решението ѝ ми се превърна в нещо като фикс идея.

Снощи "изтръбуших" интернета в търсене на интелигентно решение и попаднах на още няколко места, където се обсъжда този казус, но никъде нямаше готов алгоритъм за решаването му.

В крайна сметка се наложи да си припомня математиката и да използвам нещата, които вече бях открил като подсказки по задачата, а именно:

1. Задачта има решение (70279608 ) - линк, линк2, линк3, линк4

2. От линковете в т.1 и от коментара на kolioi става ясно как се проверява това решение:

70279608 * log 2 = 21156270.091506298118993045735591

10 ^ 0.091506298118993045735591 = 1.234543218330957522614340958985

Остана ми само да тръгна по обратния ред и стигнах до това решение на C++, което успява да намери резултата за под 20 секунди на моята машина (i5 2.3GHz):

#include<iostream>
#include<cmath>
#include<climits>

int main()
{
    const double log_2 = 0.30102999566398119521373889472449;

    double intpart;

    for(int i = 0; i < INT_MAX; i++)
    {
        if (123454321 == int(pow(10.0, modf(i * log_2, &intpart)) * 100000000.0))
        {
            std::cout << "Found it = " << i << std::endl;
            break;
        }
    }

    return 0;
}

Found it = 70279608

Process returned 0 (0x0)   execution time : 11.737 s
Press any key to continue.

Сметките в решението със сигурност може да се оптимизират и сигурно ще го направя, но реших първо да го споделя, в случай ,че още някой си губи съня от тази задача.

Поздрави!

07/05/2017 12:40:54 07/05/2017 12:53:23

vlad.dinev 13 Точки

MartinBG, я пробвай това

#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <time.h>

#pragma GCC optimize("O3")

#define GOAL  123454321
#define TOINT 100000000.0

int main(void)
{
	int i;
	double d;
	register const double LOG2 = 0.30102999566398119521373889472449;

	clock_t begin = clock();
    for(i = 0; i <= INT_MAX; i++)
	{
		d = i * LOG2;
		if (GOAL == (int)(pow(10.0, d - (int)d) * TOINT))
			break;
	}
	clock_t end = clock();
	
	printf("%d\n", i);
	printf("Time: %.2f sec\n", (double)(end - begin) / CLOCKS_PER_SEC);

    return 0;
}

и сподели колко ти изкарва.

Алгоритъмът, който ползваш, изглежда да е най-ефективният познат (така пише в нета :)

Като микро оптимизации съм махнал modf() и константата съм я дефинирал като register. Това подсказва на компилатора да държи стойността в някой от регистрите, с което обаче може и да не се съобрази. Викането на функция в цикъл винаги бави (особено, ако ще се вика 70 милиона пъти), така че е хубаво да се елиминира до колкото може. O3 флага сваля към 0.01% от времето (поне при мен).

На i5 3.2GHz най-бързо се сметна за 5.39s

Поздрави!

07/05/2017 23:10:29 07/05/2017 23:20:10

MartinBG 4803 Точки

@vlad.dinev

Благодаря за включването в темата! :)

Замяната на modf() с "d - (int)d" е добра идея! Не знам как съм пропуснал да го направя, при условие, че знам за този метод и съм го използвал многократно.

Не знаех за register директивата при декларирането на променливи - пак научих нещо ново! :)

Въпреки оптимизациите, обаче, времето за изпълнение на двете програми на моя лаптоп е горе-долу еднакво - около 15 секунди.

Това най-вероятно е заради спецификите на лаптопа и Power management-a му. На "нормална" система твоята версия на програмата би следвало да се представи по-добре от моята.

Поздрави!

08/05/2017 01:00:08

vlad.dinev 13 Точки

@MartinBG моля, пак заповядай. До сега не се бях сблъсквал с тази задача, научих нещо ново.

При мен разликата между твоята и моята версия е към 1.5s

Ще я пробвам после и на по-слаба машина и ще споделя, че ми стана интересно.

Поздрави!

08/05/2017 01:08:03

MartinBG 4803 Точки

Пробвах двете версии и на настолното си PC (i5, 2.6-3.2GHz) и твоята е по-бърза с около 1 секунда (7.1 vs 8.1s) или около 15%, както се очакваше.

Поздрави!

08/05/2017 01:54:15

vlad.dinev 13 Точки

@MartinBG такаа, пробвах твоя и моя код копирани от тук и получих следното:

64bit Dual Core Intel Pentium 2117U @ 1.8GHz:

MinGW GCC 5.3.0 - 16.6 s и 10.5 s

TDM GCC 5.1.0

64 битов код - 13.2 и 12.1

32 битов код - 12.8 и 11.9

64bit Quad Core ARMv8 @ 1.2GHz:

GCC 4.2.9 - 34.4 s и 32.5 s

Разликите варират доста, особено при първия тест. C++ кода така написан се предполага да е по-бавен, но чак пък с 1/3 по-бавен е странно. Помислих, че може да е заради линкването, TDM линква статично по default, та пробвах да линкна статично и динамично с TDM и с MinGW, но осезаема разлика нямаше.

Изводът е, че кодът е важен, но компилаторa повече. Ама недей леж' на тая кълка :)

08/05/2017 05:20:45 08/05/2017 05:22:06

Виж всички отговори