cancel
Showing results for
Did you mean:
Visitor
2,950 Views
Registered: ‎09-14-2017

## Square root of an 80bit number

Hi all,

I can't use the CORDIC module has it takes at most 48bit. I have already checked my equations, but I could not find a way to reduce the number of bit.

Any idea on how to solve? Besides having to reimplement the square root from scratch.

Thanks

Tags (4)
1 Solution

Accepted Solutions
Highlighted
Scholar
4,682 Views
Registered: ‎06-21-2017

## Re: Square root of an 80bit number

Factor your number into 2 parts and find the square root of each, then multiply the two square roots.  Make your life easier and make one of your factors 2^32.  This should get you down to the 48 bits you need for a CORDIC.  The division for the factoring is a right shift and the multiply at the end is a left shift.

7 Replies
Highlighted
Scholar
4,683 Views
Registered: ‎06-21-2017

## Re: Square root of an 80bit number

Factor your number into 2 parts and find the square root of each, then multiply the two square roots.  Make your life easier and make one of your factors 2^32.  This should get you down to the 48 bits you need for a CORDIC.  The division for the factoring is a right shift and the multiply at the end is a left shift.

Highlighted
Visitor
2,916 Views
Registered: ‎09-14-2017

## Re: Square root of an 80bit number

Great! That's a good one. The following questions then is: where to split?

In my 80bit highly unlikely I will have bit set in the highest part, but at the same time, those few, will have a higher weight. How to go?
Highlighted
Visitor
2,915 Views
Registered: ‎09-14-2017

## Re: Square root of an 80bit number

What I meant with the previous message is that because of the splitting loss of precision is expected. How to minimise it? As I said I can't assume an uniform distribution in the it of my number, but then what distribution would fit best?
Highlighted
Teacher
2,903 Views
Registered: ‎07-09-2009

## Re: Square root of an 80bit number

this might help,

http://www.wikihow.com/Calculate-a-Square-Root-by-Hand

to get the number small, find if its above a certain number then you know what one of the factors is

this might also be possible , though I have not done this

http://www.basic-mathematics.com/square-root-algorithm.html

another interesting one is here

https://doc.lagout.org/security/Hackers%20Delight.pdf

17-4

Highlighted
Voyager
2,892 Views
Registered: ‎06-24-2013

## Re: Square root of an 80bit number

where to split?

2^(MSB(x)/2) ... for even MSB(x)/2 and

2^(MSB(x)/2 - 1) ... for odd MSB(x)/2 where MSB(x) is the highest bit set

For example, if the MSB(x) is 63, then your factor would be 2^30.

Note: you can handle both cases by simply ignoring bit 0 of MSB(x)/2.

Best,

Herbert

-------------- Yes, I do this for fun!
Highlighted
Guide
2,876 Views
Registered: ‎01-23-2009

## Re: Square root of an 80bit number

Factor your number into 2 parts and find the square root of each, then multiply the two square roots.  Make your life easier and make one of your factors 2^32.

I don't see how this works...

If the number in question is divisible by 2^32 then that is fine. But if not, dividing your original 80 bit number by 2^32 still results in an 80 bit number, but with 32 fractional digits. If you simply drop these fractional digits, you no longer have the precision of the original number.

For this to work, you would actually have to find an integer factor of the original 80 bit number that is larger than or equal to 2^32 - I have no idea how one would go about doing this... If you could find such a factor, then you could take the square root of both and multiply them...

Avrum

Highlighted
Scholar
2,812 Views
Registered: ‎06-21-2017