Making Code faster

[carl89]

Hi Guys,
I've posted my code and what it supposed to do inside the code as a comment.
In my opinion it seems working. But It takes forever to find the match, Is the any way someone can make this code faster?

Guys, Just for more clarification, Here is what i'm trying to do:
Lets say my original number is 73.
Double the number is 146.
Now if i flip the original number's last digit then it will become 37.
now if i match flipped number and double number which is 146 so 37!=146.
so my code is supposed to find the number that is equal.


Thanks

#include <iostream>
#include <cmath>

using namespace std;
/*
 ********************************************************************************** 
 *                                                                                *
 *This code is suppoded to take a number flip the last digit of that number then  *
 *Doublr the original number and match those two numbers and return it to user.   *
 *                                                                                *  
 **********************************************************************************  
 */
unsigned long long int flip( unsigned long long int n )
{
	unsigned long long int digit = n % 10;
	unsigned long long int r = n; 
	while ( r /=10 ) digit *= 10;
	n = digit + n / 10;

	return ( n );
}
/*IGNORE this for NOW*/
/*
void flip(unsigned long long int &no)
{
unsigned long long int c=1,s=no%10;
no/=10;
while(pow(10,c++)<no);
no+=s*pow(10,c-1);
}
*/
int main(){
  unsigned long long int reverse_number=0, twice_number =0;  
  for(unsigned long long int i = 1; i< 421052631578947368ull;i++){
  twice_number = i*2;
  reverse_number = flip(i);
  
  if(reverse_number == twice_number)
  {
	cout<<"Match found :"<<"Original ->"<<i<<" Reverse ->"<<reverse_number<<" Double ->"<<twice_number<<endl;
	break;
  }
  else{
		cout<<"Scanning..."<<endl;
	  }
}
	  
 
return 0;
}

[KRAkatau]

First idea would be to use base-10 logarithm to determine what is the order of the number.

It should look like this:

#include <math.h>
unsigned long long int flip( unsigned long long int n )
{
    unsigned long long int digit = n % 10;
    int order = (int)log10l((long double)n);

    return digit * (unsigned long long int)pow(10.0, order) + n / 10;
}

I think precision of representation in doubles should be enough to correctly compute the logarithm and power. However, in your place I would run both functions on some really large numbers at the end of your range and compare the results to check if it does work.

[KRAkatau]

Also you may think of some alpha-tests such as:
- if the first digit is >= 5 then the match is impossible
- after multiplication the first digit (say, d) will change to either (2 * d) or (2 * d + 1), so if the last digit is not equal to either, then match is impossible (this actually kinda includes the first one though :))

Sometimes brute force is not the best way :)

By the way, do you need to find one match or all the matches in that really big range?

[Lowest0ne]

Remove this:
cout<<"Scanning..."<<endl;

[ToniAz]

Copy/paste the body of your function in main, or use inline.
change i*2 into i << 1, although I think the compiler already does that.

[JLBorges]

Hmm... Interesting!

As the numbers become large, any brute force algorithm is going to be computationally horrendous.

Say, the first digit of N is F in [1,4]
The last digit of N, L must be F*2
The second last digit SL of N must be L*2%10 with a carry of L*2/10
And so on ...
Till the second digit of N is equal to F/2, and the first digit is F

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

enum { MULTIPLIER = 2, RADIX = 10 } ;

std::vector<int> digits_of_2n( int first_digit_of_2n )
{
    int last = first_digit_of_2n * MULTIPLIER ;
    std::vector<int> digits( 1U, last % RADIX ) ;
    int carry = last / RADIX ;

    while( digits.back() != first_digit_of_2n / MULTIPLIER || carry != 0 )
    {
        last = digits.back() * MULTIPLIER + carry ;
        digits.push_back( last % RADIX ) ;
        carry = last / RADIX ;
    }

    digits.push_back(first_digit_of_2n) ;
    std::reverse( digits.begin(), digits.end() ) ;
    return digits ;
}

std::vector<int> digits_of_n( const std::vector<int>& digits_2n )
{
    std::vector<int> digits_n ;
    int carry = 0 ;
    for( int digit : digits_2n )
    {
        digit = digit + carry * RADIX ;
        carry = digit % MULTIPLIER ;
        digits_n.push_back( digit / MULTIPLIER ) ;
    }
    return digits_n ;
}

int main()
{
    for( int first_digit_of_2n = MULTIPLIER ; first_digit_of_2n < 9 ; first_digit_of_2n += MULTIPLIER )
    {
        std::vector<int> digits_2n = digits_of_2n(first_digit_of_2n) ;
        for( int digit : digits_of_n(digits_2n) ) std::cout << digit ;
        std::cout << " * " << MULTIPLIER << " == " ;
        for( int digit : digits_2n ) std::cout << digit ;
        std::cout << '\n' ;
    }
}

Output:

105263157894736842 * 2 == 210526315789473684
210526315789473684 * 2 == 421052631578947368
315789473684210526 * 2 == 631578947368421052
421052631578947368 * 2 == 842105263157894736

[carl89]

Thank you for Solving my problem, Yet.
It still gives me errors while i compile this code on my machine.
I use "g++" as my compiler and compiled it on Linux Mandriva.
I posted my errors, Thanks

[jatin@localhost Desktop]$ g++ -Wall reverse.cpp
reverse.cpp: In function ‘std::vector<int, std::allocator<int> > digits_of_n(const std::vector<int, std::allocator<int> >&)’:
reverse.cpp:29: error: expected initializer before ‘:’ token
reverse.cpp:35: error: expected primary-expression before ‘return’
reverse.cpp:35: error: expected ‘;’ before ‘return’
reverse.cpp:35: error: expected primary-expression before ‘return’
reverse.cpp:35: error: expected ‘)’ before ‘return’
reverse.cpp:28: warning: unused variable ‘carry’
reverse.cpp: In function ‘int main()’:
reverse.cpp:43: error: expected initializer before ‘:’ token
reverse.cpp:45: error: expected primary-expression before ‘for’
reverse.cpp:45: error: expected ‘)’ before ‘for’
reverse.cpp:45: error: expected initializer before ‘:’ token
reverse.cpp:47: error: expected primary-expression before ‘}’ token
reverse.cpp:47: error: expected ‘)’ before ‘}’ token
reverse.cpp:47: error: expected primary-expression before ‘}’ token
reverse.cpp:47: error: expected ‘;’ before ‘}’ token

[JLBorges]

> I use "g++" as my compiler and compiled it on Linux Mandriva.

First try compiling with a -std=c++11 option. For example:
$ g++ -std=c++11 -Wall -pedantic -Wextra -O3 -o reverse reverse.cpp && ./reverse

If that doesn't work - error: unrecognized option "-std=c++11", the compiler is old, and the range-for loops need to be replaced with C-style for loops.
http://www2.research.att.com/~bs/C++0xFAQ.html#for

// ...

std::vector<int> digits_of_n( const std::vector<int>& digits_2n )
{
    std::vector<int> digits_n ;
    int carry = 0 ;

    // for( int digit : digits_2n ) // ------
    for( std::size_t i = 0 ; i < digits_2n.size() ; ++i ) // ++++++
    {
        int digit = digits_2n[i] ; // ++++++

        digit = digit + carry * RADIX ;
        carry = digit % MULTIPLIER ;
        digits_n.push_back( digit / MULTIPLIER ) ;
    }
    return digits_n ;
}

int main()
{
    for( int first_digit_of_2n = MULTIPLIER ; first_digit_of_2n < 9 ; first_digit_of_2n += MULTIPLIER )
    {
        std::vector<int> digits_2n = digits_of_2n(first_digit_of_2n) ;

        // for( int digit : digits_of_n(digits_2n) ) std::cout << digit ; // ------
        std::vector<int> digits_n = digits_of_n(digits_2n) ; // ++++++
        for( std::size_t i = 0 ; i < digits_n.size() ; ++i ) // ++++++
               std::cout << digits_n[i] ; // ++++++

        std::cout << " * " << MULTIPLIER << " == " ;

        // for( int digit : digits_2n ) std::cout << digit ; // ------
        for( std::size_t i = 0 ; i < digits_2n.size() ; ++i ) // ++++++
               std::cout << digits_2n[i] ; // ++++++

        std::cout << '\n' ;
    }
}

And then compile with a -std=c++98 option. For example:
$ g++ -std=c++98 -Wall -pedantic -Wextra -O3 -o reverse reverse.cpp && ./reverse

In either case, make sure that you understand the logic, and then try to write the program on your own, using constructs that are familiar to you - it will then become your program.