C++

Forum

 
Recursion handling.

wtf (670)
I always figured that it would be easier to speed up certain recursive functions by using a 'recursive handler', that is to say, something that handles recursion.

So i have this code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#include <cstdio>
#include <time.h>
#include <windows.h>
using namespace std;

typedef long very;

very long rh_factorial(very long num);
very factorial(very num);
bool clearbuf();

int main()
{
    printf("Good day.\n");
    bool wieder = -1;
    very long n;
    do
        {
            reenter:
            printf("\nEnter a number to get the factorial of.\n>");
            if (!scanf("%d", &n))
                {
                    clearbuf();
                    goto reenter;
                }
            very long timer_rhf = 0, timer_f = 0, starttimer_rhf = 0, starttimer_f = 0, rhf = 0, f = 0;
            starttimer_rhf = clock();
            rhf = rh_factorial(n);
            timer_rhf = clock() - starttimer_rhf;

            starttimer_f = clock();
            f = factorial(n);
            timer_f = clock() - starttimer_f;

            printf("\nThe handled factorial of %d is %d.\n", n, rhf);
            printf("\nThe straight factorial of %d is %d.\n", n, f);
            printf("\nIt took %d milliseconds to compute %d handled recursively.\n", timer_rhf, rhf);
            printf("It took %d milliseconds to compute %d without recursion handling.\n", timer_f, f);
            recatch:
            printf("\nAnother? 0 for no 1 for yes.\n>");
            if (!scanf("%d", &wieder) || (wieder < 0 || wieder > 1))
                {
                    clearbuf();
                    goto recatch;
                }
        }while(wieder);
    printf("Thank you.\n");
    return 0;
}

very long rh_factorial(very long num)
{
    Sleep(10);
    static very long base = 3, base_factorial_saved = 6;
    if (num < base)
        {
            base = 3;
            base_factorial_saved = 6;
        }
    if (num == 0)
        return 1;
            else if (num == 1)
                return 1;
                    else if (num == 2)
                        return 1;
                            else if (num == base)
                                return base_factorial_saved;
                                    else
                                        {
                                            int rv = num*(rh_factorial(num-1));
                                            if (rv > base)
                                                {
                                                    base = num;
                                                    base_factorial_saved = rv;
                                                }
                                            return rv;
                                        }
}

very factorial(very num)
{
    Sleep(10);
    if (num == 0)
        return 1;
    if (num == 1)
        return 1;
    if (num == 2)
        return 2;
    else return num*(factorial(num-1));
}


That saves the result of the thus far largest called parameter to rh_factorial and relied upon it, rather than recursing down to the base relation. The result can be quite extraordinary.

For the following input:11, 12
the output:

It took 141 milliseconds to compute 39916800 handled recursively.
It took 156 milliseconds to compute 39916800 without recursion handling.

It took 32 milliseconds to compute 479001600 handled recursively.
It took 171 milliseconds to compute 479001600 without recursion handling.


Notice the difference?

I was wondering is there any reason why, despite having declared everying very long int why it can't compute accurate results beyond 12!?

Also wondering what steps I could do to speed up results for other factorials as well, not just when its the highest factorial yet computed.
Like maybe have a int * of various results predefined at certain intervals?

And lastly, does anyone know if there are any hardware implementations of this kind of 'recursion handling' in CPUS? It seems to me like there probably should be.

Anyways thanks!
shacktar (1187)
That saves the result of the thus far largest called parameter to rh_factorial and relied upon it, rather than recursing down to the base relation.

What you're describing here is caching, and it's a well known optimization technique.


I was wondering is there any reason why, despite having declared everying very long int why it can't compute accurate results beyond 12!?

You have an int multiplication here:

int rv = num*(rh_factorial(num-1));


Like maybe have a int * of various results predefined at certain intervals?

Or a growing hashmap of each factorial computed thus far. You could check if the input is in the map and if so, get the value, otherwise compute the result and place it in the map. Or you could just use a static array with the length capped at the highest factorial you can compute with a long long.


And lastly, does anyone know if there are any hardware implementations of this kind of 'recursion handling' in CPUS?

Not from the context of recursion, but CPUs do caching. Also, some compilers check to see if a recursive function does a tail-recursive call, and if so they optimize out the unwinding of the stack.
Last edited on
andywestken (4094)
I think a better test case for recursion might help.

While the calculation of a factorial is the classic text book example for recursion, it is cleaner to implement it as a loop in C++, as it saves pushing and popping the stack.

Tail end recursion can be used to implement factorial in C++, but I think it breaks the KISS Principle.
Last edited on
shacktar (1187)
Not that I would endorse its use for calculating a factorial, but I just wanted to throw it out there considering this is a discussion on recursion and optimization.
Last edited on
wtf (670)
Thanks shacktar.

I changed the int rv to very long rv and it still gives me the same (incorrect) results for 13! and higher. this is for both versions of the function.
shacktar (1187)
This works for me. My compiler didn't let me do typedef long very; with very long. I also didn't have the implementation of clearbuf(). I removed the calls to Sleep because they didn't seem necessary. Note the formats in the calls to printf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
#include <time.h>
#include <windows.h>
#include <cstdio>
using namespace std;

#define very long

very long rh_factorial(very long num);
very long factorial(very long num);
//bool clearbuf();

int main()
{
    printf("Good day.\n");
    int wieder = -1;
    very long n = 0;
    do
        {
            reenter:
            printf("\nEnter a number to get the factorial of.\n>");
            if (!scanf("%lld", &n))
                {
                    //clearbuf();
                    goto reenter;
                }
            very long timer_rhf = 0, timer_f = 0, starttimer_rhf = 0, starttimer_f = 0, rhf = 0, f = 0;
            starttimer_rhf = clock();
            rhf = rh_factorial(n);
            timer_rhf = clock() - starttimer_rhf;

            starttimer_f = clock();
            f = factorial(n);
            timer_f = clock() - starttimer_f;

            printf("\nThe handled factorial of %lld is %lld.\n", n, rhf);
            printf("\nThe straight factorial of %lld is %lld.\n", n, f);
            printf("\nIt took %lld milliseconds to compute %lld handled recursively.\n", timer_rhf, rhf);
            printf("It took %lld milliseconds to compute %lld without recursion handling.\n", timer_f, f);
            recatch:
            printf("\nAnother? 0 for no 1 for yes.\n>");
            if (!scanf("%d", &wieder) || (wieder < 0 || wieder > 1))
                {
                    //clearbuf();
                    goto recatch;
                }
        }while(wieder);
    printf("Thank you.\n");
    return 0;
}

very long rh_factorial(very long num)
{
    static very long base = 3, base_factorial_saved = 6;
    if (num < base)
        {
            base = 3;
            base_factorial_saved = 6;
        }
    if (num == 0)
        return 1;
            else if (num == 1)
                return 1;
                    else if (num == 2)
                        return 1;
                            else if (num == base)
                                return base_factorial_saved;
                                    else
                                        {
                                            very long rv = num*(rh_factorial(num-1));
                                            if (rv > base)
                                                {
                                                    base = num;
                                                    base_factorial_saved = rv;
                                                }
                                            return rv;
                                        }
}

very long factorial(very long num)
{
    if (num == 0)
        return 1;
    if (num == 1)
        return 1;
    if (num == 2)
        return 2;
    else return num*(factorial(num-1));
}


Good day.

Enter a number to get the factorial of.
>13

The handled factorial of 13 is 6227020800.

The straight factorial of 13 is 6227020800.

It took 0 milliseconds to compute 6227020800 handled recursively.
It took 0 milliseconds to compute 6227020800 without recursion handling.

Another? 0 for no 1 for yes.
>1

Enter a number to get the factorial of.
>14

The handled factorial of 14 is 87178291200.

The straight factorial of 14 is 87178291200.

It took 0 milliseconds to compute 87178291200 handled recursively.
It took 0 milliseconds to compute 87178291200 without recursion handling.

Another? 0 for no 1 for yes.
>1

Enter a number to get the factorial of.
>15

The handled factorial of 15 is 1307674368000.

The straight factorial of 15 is 1307674368000.

It took 0 milliseconds to compute 1307674368000 handled recursively.
It took 0 milliseconds to compute 1307674368000 without recursion handling.

Another? 0 for no 1 for yes.
>0
Thank you.
Press any key to continue . . .
andywestken (4094)
Note that the return of the function clock() has to be divided by CLOCKS_PER_SEC to get a time, rather than a tick count.

I tend to use a little class based on QueryPerformanceCounter to do my timing; but there does seem to be some debate about which timing method is better. And I sent to repeatedly call small algs in a loop and calc the mean, min, and max (hence range). But this might be confused by your caching strategy, I guess.

As you're Windows, you might also be interested in GetThreadTimes(). It allows you to measure the cpu time taken by an algorithm, rather than the "real world" time. This might be better for algorithm design?

This article might of interest for future reference:
http://www.codeproject.com/Articles/175033/An-eternal-question-of-timing/?display=Mobile

Andy
Last edited on
Topic archived. No new replies allowed.