Neumann's Random Generator

Question

Please read the task first: http://codeabbey.com/index/task_view/neumanns-random-generator

I have to keep track of the number of iterations, but I get very strange results. In the example after the task we have the numbers 0001 and 4100 and they should come to loop after 2 and 4 iterations. But my results are 1, 4 or if I change the place of the counter 2 or 5 but never 2 and 4. Here is my code:

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    int value;
    int counter;
    int result;
    int setvalue = 1; // use to exit the loop if setvalue == 0;
    cin >> n;
    vector<int> new_results(0); // use to store all the results from iterations
    vector<int> results_vec(0); // use to store the number of iterations for each number

    for (int i = 0; i < n ; i++)
    {

        cin >> value;
        while(setvalue == 1)
        {
            value = value*value;

            value = (value % 1000000) / 100;

            if(find(results_vec.begin(), results_vec.end(), value) == results_vec.end())
            {
                results_vec.push_back(value);
            }
            else
            {
                counter = results_vec.size();
                new_results.push_back(counter);
                setvalue = 0;
            }

        }
        results_vec.clear();


    }
    for (int i = 0; i < new_results.size() ; i++)
    {
        cout << new_results[i] << " ";
    }

}

What intermediate numbers do you generate if you start with 0001 and 4100? — tgmath, Mar 03 '14 at 12:25
For 0001 I get (0, 0) For 4100 I get (8100, 6100, 2100, 4100) — Vallerious, Mar 03 '14 at 12:46
Shouldn't you be putting the initial seed value into `results_vec` before starting your `while` loop? — pjs, Mar 03 '14 at 15:03
Wow....Thanks pjs : ))) I`ll edit the code with the correct one — Vallerious, Mar 04 '14 at 12:56

score 2 · Accepted Answer · answered Mar 03 '14 at 12:26

2

Going in and out of a string the way you have is really very ugly and extremely expensive computationally.

Use

(value % 1000000) / 100;

instead to extract the middle four digits. This works by (1) taking the modulus to remove the leading two digits then (2) removing the last two with integer division.

As it's so much simpler, I suspect that will fix your bugs too.

answered Mar 03 '14 at 12:26

Bathsheba

231,907
34
361
483

Also int is too small for 9999^2, you have to use long. – tgmath Mar 03 '14 at 12:28
@tgmath 9999^2 is just about 99,980,001 which is well below 2,147,483,647 (2^31 -1), so on the usual platforms (i.e. int has >= 32 bits) this is sufficient. Of course, the standard doesn't guarantee that int has at least 32bits: the guaranteed lower bound is 16bit. – stefan Mar 03 '14 at 12:49
Wow, thanks! Didn`t have to use that string conversion after all :) But the problem remains - when the if statement finds that the number is already in the vector, meaning that we came to a loop it doesn`t add the last number from the iteration and jumps to the else which adds it to the new_results vector. – Vallerious Mar 03 '14 at 12:52
@stefan thx. for mentioning that. int should be fine. I was confused by INT_MAX(32767==2^15-1) in climits.h. – tgmath Mar 03 '14 at 12:56
@tgmath That's indeed the standard mandated lower limit for `INT_MAX`. It's fairly rare, but exists. If one wants to be sure that `int` has at least 32 bits, `int32_t` is the appropriate type. – stefan Mar 03 '14 at 13:07
Sorry for reposting my comment but I need quick help on this. But the problem remains - when the if statement finds that the number is already in the vector, meaning that we came to a loop it doesn`t add the last number from the iteration and jumps to the else which adds it to the new_results vector – Vallerious Mar 03 '14 at 14:43
Please refactor using my suggestion and post as an edit (but do retain the original code else you invalidate answers). Then folk will be glad to help. – Bathsheba Mar 03 '14 at 14:49

score 0 · Answer 2 · answered Mar 04 '14 at 12:58

Here is the correct code, thank you for all your help.

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    int value;
    int counter;
    int result;
    cin >> n;
    vector<int> new_results(0); // use to store all the results from iterations
    vector<int> results_vec(0); // use to store the number of iterations for each number

    for (int i = 0; i < n ; i++)
    {

        cin >> value;
        results_vec.push_back(value);
        while(true)
        {
            value = value*value;

            value = (value % 1000000) / 100;

            if(find(results_vec.begin(), results_vec.end(), value) == results_vec.end())
            {
                results_vec.push_back(value);
            }
            else
            {
                counter = results_vec.size();
                new_results.push_back(counter);
                break;
            }

        }
        results_vec.clear();


    }
    for (int i = 0; i < new_results.size() ; i++)
    {
        cout << new_results[i] << " ";
    }

}

Neumann's Random Generator

2 Answers2

Linked