Best way to find the nth root of a number using VHDL.

[Akanimo]

Hi,

Considering a fixed-point binary number, and the weight of its bits, is there any formula or method for finding the nth root of such a number? I decided to keep it simple and start by considering only integers and with deducing a pattern for finding theirs squares. I hope that the pattern will be reversible, from squares to square roots. After which, I can go ahead to check that for cubes and cube roots, then ... nth power to nth root. After learning something from integers, I hope that I might be able to pinpoint something for fixed-point numbers.

I have been staring at the following to see whether I can find a pattern for a start:
Decimal number = binary; sq(decimal number) = binary
1 (base 10) = 2^(0 base 10) = 01 (base 2); 1 (base 10) = 2^(0 base 10) = 01 (base 2); -- no shift, no trailing zero
2 (base 10) = 2^(1 base 10) = 10 (base 2); 4 (base 10) = 2^(2 base 10) = 100 (base 2); --shift by one place, two trailing zeros
3 (base 10) = 2^(1 base 10) + 2^(0 base 10) = 11 (base 2); 9 (base 10) = 2^(3 base 10) + 2^(0 base 10) = 1001 (base 2); -- shift by two places, three trailing zeros and no shift, no trailing zero
4 (base 10) = 2^(2 base 10) = 100 (base 2); 16 (base 10) = 2^(4 base 10) = 10000 (base 2); -- shift by two places, four trailing zeros
5 (base 10) = 2^(2 base 10) + 2^(0 base 10) = 0101 (base 2); 25 (base 10) = 2^(4 base 10) + 2^(3 base 10) + 2^(0 base 10) = 11001 (base 2); -- shift by two places, four trailing zeros and shift by one place, three trailing zeros and no shift, no trailing zero.
And so on

Observations:
1) For every odd number, the LSB is 1. For even numbers, the LSB is 0.
2) the powers of 2 seem to play a role in finding a pattern
3) It seems like there are fundamental numbers (like 1, 2, 4, 8, etc which are powers of 2) whose patterns can be followed to build the powers of non-fundamental numbers (like 3, 5, 6, 7, 9, 10, etc which are built from fundamental numbers). Also, it seems like patterns could be deduced from powers of fundamental numbers to build powers of non-fundamental numbers.
4) etc

Please, are there anything you observe? Do you think this might be a good approach to finding a solution to this long-standing problem?

Any feedback is highly appreciated.

 

[Akanimo]

I understand that what I have written down may need further clarification. Please, if any clarification is sought here, I will provide it. Actually, I am looking for a method that can be implemented within a few clock cycles.

Please, is there any observation to make?

 

[barry]

Aside from the obvious, brute-force approach of using a look-up table, you're going to have to use some numerical method: Newton's method, bisection, etc. You might also be able to use a CORDIC.

 

[KlausST]

Hi,

First things first:
What are the requirements?
Y = N'th root of X
What is the range and resolution (calculation precision) of: X, N, Y?
What calculation speed do you expect?

****

Basically there are a couple of ways:
* tables (are the fastest?)
* interpolation
* iteration

I've one coded a fast square root calculation for AVRs
* 32 bit unsigned integer input
* 16 bit unsigned integer output
* error: max +/-1LSB of output.
Solution:
Shift, 128 entry table, calculation of difference, simplified division, shift back
It follows the mathematical formula: (A + B)^2 = A^2 + B^2 + 2AB

The idea behind in a bit different example:
If you want to find the square root of 27. ( with 8 bit fraction precision)
From the table find the squares of integers:
1, 1
2, 4
3, 9
4, 16
5, 25,
6, 36
7, 49
...and so on.
Left: an integer value (A)
Right: the square of it (X), also an integer
So to find the square root of 27 .. you first have to look on the right side if the table and find the next lower value of 27.
It is 25.
Now look at the left side of the table: it is 5. (Integer result)
Now you already know the quare root of 27 is somewhere inbetween 5 and 6.
Now take the difference of 27 and 25, it is 2.
Now divide 2 by (2 x 5) --> 2 / 10 --> 0.2 (fractional result)
So the result is: the square root of 27 is pretty close to 5 × 0.2 = 5 .2
*******
Another simple mathematical concept following the above formula: (A + B)^2 = A^2 + B^2 + 2AB
Let's say you know that the square of 256 is 65536 ...
But how simple is it to find the square of 257? ( --> A = 256, B = 1)
Simple, just by adding:
It is 65536 + (2 × 256) + 1 .. oops there is a "multiply" .. lets replace it:
--> it is 65536 + 256 + 256 + 1 --> 66049
..
From 257 to 258 ... add 257 + 257 + 1 ...
From 258 to 259 ... add 258 + 258 + 1
From 259 to 260 ... add 259 + 259 + 1
From 260 to 261 ... add 260 + 260 + 1

You may also say: from 256 to 257 ... add 256 and add 257

Klaus