Estimating recursive function's progress

Well I have to ask the obvious question...

When the entire thing should complete in less than the blink of an eye, why is there any consideration given towards showing the progress of it? It just seems like you're looking for the solution to a problem that doesn't exist. There must be something important that you left out.

The fact that I need progress indication capability should be a reliable indicator that what I'm performing unfortunately does not occur in the blink of an eye. I'm working on an arbitrary precision integer arithmetic application, and the project entails that I do NOT use 3rd party libraries. Processing million-digit values can take hours depending on the operations involved. Thus it would be helpful to have a decent estimate of the timeframe required by such large operations.

Thanks for your help.

[font="arial, verdana, tahoma, sans-serif"]
I have to say I'm not very good at this,but there is my try. [/font]

I assume this is the code you use,because on the page there were several recursive solutions :


[source lang="cpp"]
[font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"]public double Power(int a, int b) {
if (b<=0) return 0;
else if (b==1) return a;
else {
return a*Power(a,b-1);
}
[/font][/font][font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"]} [/font][/font]
[font="Verdana, Arial, Helvetica, sans-serif"][/source]
[/font]
[font="Verdana, Arial, Helvetica, sans-serif"]
[/font]
Since you mentioned that you use some BigInt class,then your "multiplication" is not a normal multiplication.
it probably depeneds on how big the numbers are.
That's why each iteration is more expensive than the previous one - because the result of Power will grow.

The proper way to determine the complexity of the function would be to determine the complexity of your multiplication.
Then you have to somehow approximate how many digits there would be in the result the last time Power returns.
So let f(x,y) be the complexity function of your multiplication,where x and y are the number of digits of the two arguments
[font="arial, verdana, tahoma, sans-serif"]
[source lang="cpp"]
[/font]
public double Power(int a, int b) { [font="Courier,"][font="Verdana, Arial, Helvetica, sans-serif"] [/font][/font]
[font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"] int result = 0;
if (b==1) result = a;
else if( b > 1){ [/font][font="Courier,"] result = a*Power(a,b-1);[/font][font="Courier,"] }[/font][font="Courier,"] [/font][/font]
[font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"] showprogress(f(digits(a),digits(result)),f(digits(a),finalResultDigitsApprox));[/font][font="Courier,"] [/font][/font]
[font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"] return [/font][font="Courier,"]result [/font][/font][font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"];[/font][/font]
[font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"]}[/font][/font]
[font="Verdana, Arial, Helvetica, sans-serif"][font="Courier,"][/source]
[/font][/font]
[font="arial, verdana, tahoma, sans-serif"]This may not be correct for your case at all,,for example the complexity function of multiplication may not depend on the number of the digits of its two arguments.[/font]
Also I guess, that depending on f ,the above could be simplified further.
For example a good ( or equivalent ) solution could be [font=Verdana, Arial, Helvetica, sans-serif]showprogress( 100 * (digits(result) / [/font][font=Verdana, Arial, Helvetica, sans-serif]finalResultDigitsApprox) , 100);[/font]

That might just be the key. I already know the recursion depth, and rule of thumb is that you can simply add the number of digits of two numbers to get the number of digits the product of their multiplication would be, minus one :

eg: 100 x 100 = 10,000

or 1000 x 1000 = 1,000,000

I can take the number of digits of 'a', say for instance 5, and the power I am raising it to 'b', say 10


10x5 = 50

I can assume that my 5 digit number, to the 10th power will be roughly 50 digits, give or take one digit.

But it gets exponentially slower with each iteration, so I'm trying to manipulate these sorts of 'linear' values using a function as you've stated, I'm just trying to flatten out the exponential curve so that my progress reports are more evenly spaced time-wise, as opposed to really close-together near the beginning few recursions and ginormous on the last few. It would just be great if I could accurately estimate from the first few iterations how long the entirety of the recursive execution will take. I've been toying with smaller numbers that take about a minute or so to calculate to try and get my progress estimation/calculation just right and it's just too far off to be even usable with numbers that will take hours to calculate.

Thanks for your input, much appreciated!

I see.
It doesn't matter what function you use though - the problem is that your "progress reports" would be updated at increasingly longer intervals.
If your "f" is correct then you would get status updates like 0.1%,0.3%,1%,10%,......,100%. I.e a function that's very steep at the end as you mentioned.

To solve this you have to call showprogress at smaller intervals,i.e more than once per iteration.
So you have to either put calls to it in your multiplication fucntion (since that is what is taking the most time), or you need a separate thread.

Then you can find two arguments for which f(a,b) = 1.
If f(a,b) = a*b , a = b = 1 ( remember a and b are the number of digits)

Now you can find how much time it takes to compute 1 unit of work. You also kniow how much time the entire execution would take - totalWork*timeToComputeOneUnit

For example :

[source lang="cpp"]
int currentWork,totalWork ;

void thread(void* data){
while( currentWork < totalWork )
if ( timer.Elapsed(timeToComputeOneUnit) ){
showprogress (currentWork ,totalWork);
// We should have computed approximately one unit of work for this time
currentWork += 1;
}
}
}

[/source]