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

Square root of an 80bit number

Jump to solution

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

0 Kudos
1 Solution

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

Re: Square root of an 80bit number

Jump to solution

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.

View solution in original post

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

Re: Square root of an 80bit number

Jump to solution

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.

View solution in original post

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

Re: Square root of an 80bit number

Jump to solution
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?
0 Kudos
Highlighted
2,915 Views
Registered: ‎09-14-2017

Re: Square root of an 80bit number

Jump to solution
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?
0 Kudos
Highlighted
Teacher
Teacher
2,903 Views
Registered: ‎07-09-2009

Re: Square root of an 80bit number

Jump to solution

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

 

 

  

<== If this was helpful, please feel free to give Kudos, and close if it answers your question ==>
0 Kudos
Highlighted
Voyager
Voyager
2,892 Views
Registered: ‎06-24-2013

Re: Square root of an 80bit number

Jump to solution

Hey @giovanni.meciani,

 

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
Guide
2,876 Views
Registered: ‎01-23-2009

Re: Square root of an 80bit number

Jump to solution

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

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

Re: Square root of an 80bit number

Jump to solution

If you need more precision, it's possible to hand code an 80 bit CORDIC.  It will be large and may need lot's of pipeline stages to make timing.

0 Kudos