Thread: Possiblity of compile time calculation

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    114

    Possiblity of compile time calculation

    Hi.. Is there any possible way of calculating some values at compile time? I have the following code of genereting upto 2000000010 palindrome numbers.
    Code:
    #include <iostream>
    #include <string>
    #include <sstream>
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <vector>
    using namespace std;
    vector<unsigned long> palindrome;
    int main()
    {
    
    for(long number=0,index=0;index<(20000000010);++number)
    {
        ostringstream stream;
        string strNumber;
        stream<<number;
        strNumber=stream.str();
        int middle=strNumber.size()/2;
        bool flag=1;
        for(int j=0,k=strNumber.size()-1;j<=middle;++j,--k){
        if(strNumber[j]!=strNumber[k])
        {
            flag=0;
            break;
        }
        }
        if(flag)
        {
            unsigned long inNumber;
            istringstream convert(strNumber);
            convert>>inNumber;
    
            ++index;
            palindrome.push_back(inNumber);
        }
    }
    int i;
    while(cin>>i&&i)
    cout<<palindrome[i]<<endl;
    
    
    }
    As you see, I have taken input from the user just after calculating the whole palindromes. So cant we calculate this at compile time? because runtime of this program is extremely slow.
    Another qs. I first tried to use array but It didnt allow 2*10^9 sized array. so what should I do whenever I need that size of array?

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Theoretically you could, but C++ will not allow compile-time arrays, unfortunately. That doesn't mean you can't computer palindrome N at compile time, so long as you do not store it.
    But if you're interested in the area, look up meta-template programming and constexpr. They allow you to do some compilations at compile time.
    As for the array, use std::vector for big arrays. But do you really need that big array? Consider techniques for reducing your memory footprint.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    What type of techniques?

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    I said that as a general term. Without knowing what exactly your problem is, I cannot recommend specific techniques.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    The problem is to find the nth palindrome number where n<=2*10^9 with maximum efficiency.

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    I was talking about precalculation because if I do that then the user can input a number and I can use the index to find the palindrome number. BTW, constexpr is only allowed in C++11. But I have to use C++98.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Then why don't you calculate some numbers (ie run the code) and hard code those numbers? This will save you a lot of time. You can store the numbers in a file. You can, for example, use the line number to represent the palindrome number, so first row = first palindrome, etc.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    thats not possible. I have to submit my solution to online judge. and they dont allow any file savings....

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Check line 13. You're got 20,000,000,010 there which is probably going to exceed the range of an int on your system, and wrap around to become negative.
    You should be getting a warning when compiling this code, and you should be fixing that.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    There's a much, much easier way to get a list of palindromes, by the way, that wouldn't rely on iterating over every number and throwing out non-palindromes.

    Hint: think about the problem in reverse. Rather than detect a palindrome, given an arbitrary number (e.g. 123) how could you create a palindrome (or two) from it?

    There is at least one way to calculate the nth palindrome without calculating any of the n-1 palindromes before it. There might be one precalculation that would speed that up but it's an array of ten numbers that you could hardcode as an array literal.

    Give it a shot, if you're really stuck I can give another hint.
    Last edited by Cat; 05-13-2013 at 06:23 PM.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  11. #11
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    I got how can I get a palindrome.. I reverse it and add it.. reverse it and add it and so on.. but the problem is, how can I know the nth palindrome this way.. what should I do with numbers like 196?

  12. #12
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    Quote Originally Posted by Tamim Ad Dari View Post
    I got how can I get a palindrome.. I reverse it and add it.. reverse it and add it and so on.. but the problem is, how can I know the nth palindrome this way.. what should I do with numbers like 196?
    Okay, here are two hints.

    1. If I were to list out the six-digit palindromes in order, they would be:

    100001
    101101
    102201
    103301
    ...
    199991
    200002
    201102
    ...
    998899
    999999

    Notice a pattern? You should very easily be able to calculate the nth palindrome of a certain length.

    2. So, let's say I have 123321. This is the 24th 6-digit long palindrome (since 100xxx is the first, 101xxx is the second, etc.) But in the overall sequence of palindromes, what number in the series is this?

    Well, it's 24 + <number of 5 digit palindromes> + <number of 4 digit palindromes> + <number of 3 digit palindromes> + <number of 2 digit palindromes> + <number of 1 digit palindromes>
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  13. #13
    Registered User
    Join Date
    Jan 2013
    Posts
    114
    owh... thanks.. I got that..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 01-12-2013, 10:11 AM
  2. Time calculation problem
    By putty88 in forum C Programming
    Replies: 4
    Last Post: 03-24-2009, 06:20 AM
  3. Time Calculation
    By Nappaa in forum Tech Board
    Replies: 1
    Last Post: 05-14-2006, 02:53 PM
  4. A possiblity of not useing tcp-ip for a lan based game?
    By CSoFun in forum C++ Programming
    Replies: 5
    Last Post: 01-31-2003, 12:02 PM