Using a While loop to converge on a value

DaveC426913

Gold Member
18,312
1,910
Summary
How preserve the last value to compare it to the new one without exiting the loop
My brain is misfiring.

I have a start value (integer) that I perform an operation on that will iteratively cause it to converge on some (unknown) integer value.
I stop the iteration when the new value is the same as the old one (i.e. it has stopped changing).
Until that happens, I keep iterating.
To know that it's converged, I set the lastVal equal to thisVal before iterating.
But as soon as I do this, it meets the criteria for exiting the loop.
So I only get one iteration.

This is JavaScript, but it works fine as pseudo-code:

Code:
                lastVal=-1
                thisVal=i;         
                while (thisVal!=lastVal){
                    thisVal = doAThingTo(thisVal);
                    counter++;
                    lastVal = thisVal; // here's the problem
                }
                prt(counter);
I tried testing it without setting it, but of course that doesn't make the problem go away:
Code:
                lastVal=-1
                thisVal=i;         
                while (thisVal!=lastVal){
                    if (doAThingTo(thisVal)) != lastVal){
                        thisVal = doAThingTo(thisVal);
                        counter++;
                        lastVal = thisVal; // still a problem
                    }
                    else{
                        //break;
                        lastVal = thisVal;
                    }
                }
                prt(counter);
What am I missing?
Maybe a third temp variable?

I guess I could do an infinite loop that breaks manually when the criteria is met...
Code:
                lastVal=-1
                thisVal=i;         
                while (true){
                    thisVal = doAThingTo(thisVal);
                    if (thisVal == lastVal) {
                        break;
                    }
                    else {
                        counter++;
                        lastVal = thisVal;
                    }
                }
                prt(counter);
 
32,838
4,562
Summary: How preserve the last value to compare it to the new one without exiting the loop

This is JavaScript, but it works fine as pseudo-code:
Code:
                lastVal=-1
                thisVal=i;        
                while (thisVal!=lastVal){
                    thisVal = doAThingTo(thisVal);
                    counter++;
                    lastVal = thisVal; // here's the problem
                }
                prt(counter);
This was your first code example, which seems to be nearly equivalent to your second example, with the difference being that you are moving the conditional expression out of while, and putting it into an if ... else structure.

The simple example to the question you're asking in the Summary is to not reset lastVal to thisVal as you're doing in the last line of your while loop in the first two examples. That is, if I understand what you're trying to do.

Can you provide a sequence of numbers that you're working with, and what the desired outcome of your program should be?
 

DaveC426913

Gold Member
18,312
1,910
I took my own advice, and took the conditional out of the while.

Code:
                thisVal=i;
                counter=0;
                while (true){
                    if (subtractHiLo(thisVal)==lastVal && counter!=0){
                        break;
                    }
                    else {
                        thisVal = subtractHiLo(thisVal);
                        counter++;
                        lastVal=thisVal;
                    }                
                }
Works great.

I am testing Kaprekar's constant.

For any integer from 0001 to 9999 (skipping homogenous numbers such as 2222 and 7777), the convergence will be on 6174, after a maximum of 7 iterations.

Attached is the text output of my JavaScript - all 9999 sequences. (I'd attach my HTML doc, but PF doesn't allow HTML or ZIP uploads.)

(Only took me about 2 hours, and most of that was unit testing my helper functions.)
 

Attachments

Filip Larsen

Gold Member
1,226
160

DaveC426913

Gold Member
18,312
1,910
Tried and tested problem-solving technique:

1. Write a post asking for help to solve the problem. Anticipate any questions and nitpicks. Provide the source in a barebones, readable format.
2. Your attempt to write the problem clearly and concisely will reveal the flaw you did not see, and you will have the answer to your own question.
3. Delete the post without sending.

Works every time. (I missed step 3.)

:oldbiggrin:


Thanks for your help.
 

DaveC426913

Gold Member
18,312
1,910
Your third example is quite common pattern when using while-loops. When it is required to loop at least once, then a do-while loop may be more concise:

Code:
lastVal = -1;
thisVal = -1;
do {
  lastVal = thisVal;
  thisVal = doAThingTo(thisVal);
} while (lastVal != thisVal);
Yep. Exactly what I tried.

Of course, that doesn't do anything to solve the problem, since the internal "lastVal=thisVal" will still trigger the break in the loop immediately after the first iteration.
 

Filip Larsen

Gold Member
1,226
160
Of course, that doesn't do anything to solve the problem, since the internal "lastVal=thisVal" will still trigger the break in the loop immediately after the first iteration.
You must be doing something else then. If doAThingTo(thisValue) returns a value that is different from thisValue then clearly lastVal != thisVal.
 

DaveC426913

Gold Member
18,312
1,910
You must be doing something else then. If doAThingTo(thisValue) returns a value that is different from thisValue then clearly lastVal != thisVal.
Ah I see. You also moved the lastVal=thisVal to immediately above the doAThingTo() line - i.e. at the beginning of the loop. In my example, I do that at the end of the loop. That's the diff.
 

DaveC426913

Gold Member
18,312
1,910
The problem is grammatical : you need an UNTIL construct, not a WHILE.
...
Javascript's version is DO WHILE :
Filip's example, post 4, shows the Do While construct.

I'll refrain from commenting on the poor choice of nomenclature.
Whose poor choice? Yours? That's OK.
 
305
83
Yeah, sorry ; got stuck in a time loop... didn't see his post.... and then deleted my post when I noticed his, without seeing your reply.

Anyways, you might find this a bit smoother : it gets rid of the - to mine eyes - awkwardness of the "-1" assignments kludges and the recursive-looking thisval = doathingto(thisval).

Code:
ints
  counter = 0,
  old_value,
  new_value = function(i).

do
  old_value = new_value,
  counter++,
  new_value = function(old_value),
while
  new_value != old_value.

print
  counter.
It looks like a superfluous function call, but the algorithm has to be primed before the loop iteration. If it was a long program you'd want to call an inline procedure which contains the function call (and probably the counter increment).

Depending on your preference, you may want to initialize counter = 1.

And no, not my nomenclature : "this" and "prev(ious)" are not semantically proximate. Or, maybe my brain's "misfiring" : I found it confusing. YMMV
 
Last edited:

DaveC426913

Gold Member
18,312
1,910
Anyways, you might find this a bit smoother : it gets rid of the - to mine eyes - awkwardness of the "-1" assignments kludges and the recursive-looking thisval = doathingto(thisval).
I went with my code that I put in post 3. It works just as hoped.

And no, not my nomenclature : "this" and "prev(ious)" are not semantically proximate. Or, maybe my brain's "misfiring" : I found it confusing. YMMV
?
No one has used "prev" or previous. We used lastVal (which, granted, is synonymous with 'previous').
 

Merlin3189

Homework Helper
Gold Member
1,386
551
It may be nicer to change the chosen construct to Do ... While, or something else, but whats wrong with just doing it in the right order for your chosen construct?

lastVal=-1
thisVal=i;
while (thisVal!=lastVal){ // check for difference
lastVal = thisVal; //preserve oldVal
thisVal = doAThingTo(thisVal); // or thisVal = doAThingTo(lastVal) sounds nicer to me
counter++;
}
prt(counter);
 

Related Threads for: Using a While loop to converge on a value

Replies
5
Views
4K
Replies
7
Views
6K
  • Last Post
Replies
15
Views
3K
Replies
7
Views
5K
  • Last Post
Replies
6
Views
2K
Replies
8
Views
1K
  • Last Post
Replies
4
Views
2K
Top