You are not logged in. Please login at www.codechef.com to post your questions!

×

Dynamic programming

using dynamic programming helps to reduce the time complexity of my recursive algorithm. how this actually happens? Is it possible to find factorial in less time with dynamic programming? (the largest value of the output is 10^14)

asked 22 Dec '16, 16:34

neget's gravatar image

2★neget
628
accept rate: 14%

edited 22 Dec '16, 17:41

sorry that was a typing mistake.

(22 Dec '16, 17:44) neget2★

If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function

does not have side effects and does only depend on its parameters (i.e. not on some state). It will save you time if (and only if) the function is called with the same parameters over and over again. Popular examples include the recursive definition of the Fibonacci numbers, that is

f(0)=0

f(1)=1

f(n+2)=f(n+1)+f(n), n≥0

When evaluated naively, ff is called exponentially often. With memoisation, f(n)f(n) has always been computed by f(n+1)f(n+1) already, thus only a linear number of calls remains.

link

answered 22 Dec '16, 17:20

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

edited 22 Dec '16, 17:23

As far as i know there is no Dynamic Programming solution for finding factorials. You can look at this post for finding factorial of large numbers.

link

answered 22 Dec '16, 17:09

coder_voder's gravatar image

2★coder_voder
593332
accept rate: 8%

@neget I don't think you will be able to store the factorial of number like $10$^$14$ since even Python can't also store/calculate it! Btw you can also look here : http://stackoverflow.com/questions/26989075/approaching-dynamic-programming

@only4 Memory Saving Tip: You don't need the whole array. You could just use two variables for calculating the factorial.

link

answered 22 Dec '16, 17:27

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

edited 22 Dec '16, 17:55

And for factorial here's the code

#include <cstring>

include <iostream>

include <cstdlib>

define ll long long

using namespace std;

int result[1000] = {0};

ll fact_dp(int n)

{

if (n >= 0) 
{
    result[0] = 1;
    for (int i = 1; i <= n; ++i) 
    {
        result[i] = i * result[i - 1];
    }
    return result[n];
}

}

link

answered 22 Dec '16, 17:24

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

edited 22 Dec '16, 17:25

@only4 your program fails for larger values. Even after changing ints to long long it works only till 20.

(22 Dec '16, 17:36) coder_voder2★

I don't think finding factorial of integers -> 10^14 is possible. I thinks it's a typo.

(22 Dec '16, 17:39) only44★
2

I think you program is same as using 2 variables for finding factorial.

(22 Dec '16, 17:44) coder_voder2★

@nikhil_chandak Yes but I think calling the function again and again takes more time than this, so this is time efficient. Please correct me if I am wrong.

link

answered 22 Dec '16, 17:37

only4's gravatar image

4★only4
1.5k212
accept rate: 17%

@only I didn't mean recursion. I meant:

ans = 1 for (int i = 2; i <= n; ++i) { ans *= i ; } return ans

I have removed the if clause. Hope this helps :)

If you didn't understand, feel free to ask me!

link

answered 22 Dec '16, 17:45

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

edited 22 Dec '16, 17:46

Thanks I got you.

(23 Dec '16, 07:52) only44★

You could speed up the multiplication by using karatsuba method for multiplication of large numbers. But multiplication is already assumed to be O(1). So for factorial I don't think you can do better than O(n) whether you use dynamic programming or not. Using dp you can just avoid recalculation of factorials, but you have to build the factorial table in linear time first. That's the best you can do. So in 1 sec,

If you want the factorial

20! in C,C++ ; (10^5)! in python

If you want modular factorial

(10^7)! in C C++ python (that's the best you could do)

link

answered 22 Dec '16, 19:10

satannitr's gravatar image

3★satannitr
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,214
×90

question asked: 22 Dec '16, 16:34

question was seen: 1,432 times

last updated: 23 Dec '16, 07:52