2014:large_integer_exponentiation
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
2014:large_integer_exponentiation [2014/12/17 21:06] promnius |
2014:large_integer_exponentiation [2014/12/17 21:25] (current) promnius |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Large Integer Hardware Exponentiation ====== | ====== Large Integer Hardware Exponentiation ====== | ||
| - | {{ :2014:1.jpg?500 |}} | ||
| ===Abstract=== | ===Abstract=== | ||
| Exponents are a common mathematical operation. By hand, they're not too hard to evaluate. On a CPU, its fully possible to evaluate them as repeated multiplication. But what happens when the exponent is a 1000 digit number? What happens when the base is a 1000 digit number? What about both? Repeated multiplication may not be the smartest or fastest idea. It turns out there are far more efficient methods of evaluating large integer exponentiation by actually building separate dedicated hardware units. I chose to research different reasons/ techniques for doing exponentiation, and then design my own hardware exponential evaluator. | Exponents are a common mathematical operation. By hand, they're not too hard to evaluate. On a CPU, its fully possible to evaluate them as repeated multiplication. But what happens when the exponent is a 1000 digit number? What happens when the base is a 1000 digit number? What about both? Repeated multiplication may not be the smartest or fastest idea. It turns out there are far more efficient methods of evaluating large integer exponentiation by actually building separate dedicated hardware units. I chose to research different reasons/ techniques for doing exponentiation, and then design my own hardware exponential evaluator. | ||
| Line 8: | Line 7: | ||
| ==Software Example== | ==Software Example== | ||
| Py BigNum | Py BigNum | ||
| + | |||
| def expt_bin_rl(a, b): | def expt_bin_rl(a, b): | ||
| r = 1 | r = 1 | ||
| Line 26: | Line 26: | ||
| ==Schematics== | ==Schematics== | ||
| - | {{ :2014:2.jpg?500 |}} | + | {{:2014:img_0329_b.jpg?500|}} |
| - | EXPLANATION HERE | + | |
| + | {{:2014:img_0332.jpg?500|}} | ||
| + | |||
| + | In the top image, a basic input conditioning circuit is seen. It doesn't implement any real standard, but it gets the job done. A and B can be clocked in serially, with a chip select pin to disable computation while new values are clocked in. My implementation doesn't have a 'calculation finished' flag, but it wouldn't be too difficult to add. Instead, my implementation relies on the fact that X^0 = 1, and Y*1 = Y. Therefore, once every bit has been shifted out (so B = 0), further computations won't change the result at all. | ||
| + | |||
| + | In the bottom image, the basic computation circuit is seen. bits are serially clocked out of B, which are then used to determine if result is increased or not. If not, it is multiplied by 1. If so, it is multiplied by the 'A' register, which is equal to A^N where N is some power of 2. The 'A' register is increased each clock cycle by multiplying A by itself (giving the geometric series of A^N for N= some power of 2). | ||
| ===Difficulties=== | ===Difficulties=== | ||
2014/large_integer_exponentiation.1418868374.txt.gz · Last modified: 2014/12/17 21:06 by promnius
Page Tools
