Sign in to follow this  
deftware

Estimating recursive function's progress

Recommended Posts

So I wrote a power function ala: [url="http://osix.net/modules/article/?id=696"]http://osix.net/modules/article/?id=696[/url]

and I would greatly prefer to implement a form of progress indication with this function.

I started by calculating the total iteration depth that the function will reach, before starting the recursion.

Then I track the current depth, but each iteration is longer than the one before it, maybe ~4x longer than the previous one.

I have a showprogress(int progress, int total) function that I call in the middle of each iteration after some work has been done, before entering the next iteration.

I have manipulated the values using sqrt, squaring, etc.. but I can't seem to figure a good way to warp the linear values to align better with the actual work that is being done.. The end result is that my ETA increases with each iteration, and the whole execution completes beyond any ETA from any iteration. I've successfully hacked together good progress/total manipulation before, but this particular instance is baffling me. Any ideas ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
[font="arial, verdana, tahoma, sans-serif"][size="2"]
I have to say I'm not very good at this,but there is my try. [/size][/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"][size="2"]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.[/size][/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]

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this