how to make my execution faster? optimizations?

[ronnieaka]

firstly, please suggest some tags i should put for this post.

onto the problem..
i saw this programming problem on projecteuler.net and wanted to solve it for fun.
i solved it, but i tried first till 142857
the output was good, ok, satisfying

here's the link where the problem is posted.
http://projecteuler.net/index.php?section=problems&id=168

but as the problem specifies, we have to calculate the sum of all those kind of numbers, and display the last 5 digits of that sum. now i don't know if that can be done quicker mathematically using some reductions are series stuff. my solution is taking up like around 2minutes to output the next number having that property after it reaches upto 111111111 (9 times 1)
and it stopped at 10 times 1 (1111111111)

edit: i forgot to declare the paramater of the getNumberLength() function as unsigned long long.
it might go beyond 10x 1s i guess then

so how do i make it faster? some high level maths to reduce the prediction of sum's last 5 digits to a fewer iterations or do i need some compiler optimization..
hell i don't even know what i'm talking about xD when it comes to optimizations.
i have a 32 bit core2duo intel p8600 processor,if that might help in any thing for explaining the slowing down of the execution

i know i'm a lousy programmer, i use many unnecessary variable declarations,iterations, inefficient loops etc. my friends tell me that all the time. but i'm only learning
here's the code

#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;

int getNumberLength(unsigned long long n)
    {
        int c=0;
         while(n>0)
         {
                   n/=10;
                   c++;
         }
         return c;
    }  
    
int main()
{
unsigned long long i = 10;
unsigned long long temp;
unsigned long long j=(long)pow(i,100);
cout<<"J="<<j<<endl;
unsigned long long sum=0;
            
                   
                   
    while(i<=j)//upto 142857 it was fine, normally fast. when set to j, time went upto //like 11 minutes i guess
    {
               temp=((i%10)*(pow(10,getNumberLength(i)-1))+(i/10));
               
               if(temp%i==0)
               {cout<<i<<"\t"<<temp<<endl;
               sum+=i;
               }
    i++;
}

cout<<"\n\n Sum:"<<sum;
cout<<"\n\n last five digits:\t";
temp=sum;i=1;

while(sum>10)
{
sum/=10;i*=10;
}
cout<<(temp-(sum*i));
getch();

    return EXIT_SUCCESS;
}

[nezachem]

Just wonder what does it print at line 23... Do you realize that 10^100 takes 30+ bytes as an integer?

For the rest, read the math.

[vijayan121]

See http://en.wikipedia.org/wiki/Cyclic_number#Construction_of_cyclic_numbers

[ronnieaka]

thank you nezachem, i realized that last night after i took a long look at the problem after posting here. ;)

this stuff,then i guess, is some maths requiring problem, ain't it?:yawn:
well i guess a mere maths mortal like me can't do it then (totally 'cause i don't go deep in maths much)

but hey even if i had to print 10^100, how would i do about doing it? store in an array upto a limit of a long and then another long variable? :icon_question:

also how would you go about solving this problem? high level maths loaded c++ or what?
do tell me some ideas

[TrustyTony]

Just wonder what does it print at line 23... Do you realize that 10^100 takes 30+ bytes as an integer?

For the rest, read the math.

Did not do this yet but the math is actually in http://en.wikipedia.org/wiki/Cyclic_permutation_of_integer

[ronnieaka]

thanks to all

but i think i'm gonna pass out on completing this problem.
actually i implemented the algo on the wiki, from the first link. but it didn't print anything

[TrustyTony]

Put print earlier or inside loop. Proove the given example is found. Do loop based on power of 10, increase the power in steps and do estimate of the growing of the running time for 10 to 100.

[vijayan121]

> even if i had to print 10^100, how would i do about doing it?
> store in an array upto a limit of a long and then another long variable?

It would be simpler to store each digit separately in an array or vector.

> but i think i'm gonna pass out on completing this problem.
> actually i implemented the algo on the wiki, from the first link.
> but it didn't print anything

I think you are giving up far too soon. Programming in general is not particularly difficult, though it would appear so to someone starting out.

For example, the algorithm given in wiki is quite easy to implement once you work out how to keep track of the digits of a large integer (bigger than what an int can hold).

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>

// based on sieve of sundaram (naive implementation)
std::vector<int> generate_primes_not_divisible_by_10( int N )
{
    const int M = N / 2 ;
    std::vector<bool> sieve( M, true ) ;
    for( int i = 1 ; i < M ; ++i )
    {
        const int L = (M-i) / ( 2*i + 1 ) ;
        for( int j = i ; j <= L ; ++j )
            sieve[ i + j + 2*i*j ] = false ;
    }

    std::vector<int> primes ;
    primes.push_back(3) ;
    primes.push_back(7) ;
    // ignore 2 and 5; now add 11 upwards:
    for( int i = 5 ; i < M ; ++i )
        if( sieve[i] ) primes.push_back( i*2 + 1 ) ;
    return primes ;
}

int main()
{
    enum { MAX_DIGITS = 10000, DIGITS_TO_PRINT = 30 } ;
    std::vector<int> primes = generate_primes_not_divisible_by_10(MAX_DIGITS+1) ;

    // algorithm from wiki reproduced verbatim for b == 10
    // http://en.wikipedia.org/wiki/Cyclic_number#Construction_of_cyclic_numbers
    // (except for collecting the digits one by one into a vector)
    for( std::vector<int>::size_type i = 0 ; i < primes.size() ; ++i  )
    {
        int prime = primes[i] ;
        int remainder = 1 ;
        std::vector<int> number ;
        while( true )
        {
            // one step in long division to get the next digit (dividend==1)
            // http://www.mathpath.org/Algor/algor.long.div.htm
            int next = remainder * 10 ;
            int digit = next / prime ;
            remainder = next % prime ;
            number.push_back(digit) ; // wiki: n = n * 10 + d ;

            if( remainder == 1 ) break ; // the digits will now start repeating
        }

        // p-1 is the digital period of 1/p if p is a full reptend prime
        if( number.size() == prime-1 )
        {
            static int cnt = 0 ;
            std::cout << std::setw(4) << ++cnt << ". " ;
            // print out least significant 'DIGITS_TO_PRINT' digits
            std::for_each( number.size() < DIGITS_TO_PRINT ?
                              number.begin() : number.end()-DIGITS_TO_PRINT,
                           number.end(), [] ( int digit ) { std::cout << digit ; } ) ;
            std::cout << " [ full reptend prime " << prime << ", "
                      << number.size() << " digits ]\n" ;
        }
    }
}

[ronnieaka]

vijayan121 thanks for that
but honestly i don't have any idea what you have done here. i don't know any vector type and don't know enums.
but thank you for your effort

i'm sorry you might be feeling wasted about this, but maybe someone else could use this.

i think i'm better off coding applications, rather then just solve such problems which has to use some advanced level stuff

also, when i straightaway compiled this on Dev C++, i got 3 errors. on line 60
2 of them were:
expected primary-expression before '

and one was this:
expected primary-expression before "int"

[TrustyTony]

if you replace

[] until } at line 60

with name

print

and define the print:

void print(int digit) { std::cout << digit ; }

The code seems to work with Code::Blocks in Linux.

[ronnieaka]

that worked thanks.

but still i don't get ,whats the use of these numbers in general? i mean their property?

here's a sample output

142857 [ full reptend prime 7, 6 digits ]
0588235294117647 [ full reptend prime 17, 16 digits ]
052631578947368421 [ full reptend prime 19, 18 digits ]
0434782608695652173913 [ full reptend prime 23, 22 digits ]
0344827586206896551724137931 [ full reptend prime 29, 28 digits ]
510638297872340425531914893617 [ full reptend prime 47, 46 digits ]
898305084745762711864406779661 [ full reptend prime 59, 58 digits ]
983606557377049180327868852459 [ full reptend prime 61, 60 digits ]
082474226804123711340206185567 [ full reptend prime 97, 96 digits ]
036697247706422018348623853211 [ full reptend prime 109, 108 digits ]