Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Community Forums
- :
- Forums
- :
- Vivado RTL Development
- :
- Design Entry
- :
- Square root of an 80bit number

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

giovanni.meciani

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 04:26 AM

2,950 Views

Registered:
09-14-2017

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

1 Solution

Accepted Solutions

Highlighted
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.

bruce_karaffa

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 04:47 AM

4,682 Views

Registered:
06-21-2017

7 Replies

Highlighted
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.

bruce_karaffa

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 04:47 AM

4,683 Views

Registered:
06-21-2017

Highlighted
##

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?

giovanni.meciani

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 06:00 AM

2,916 Views

Registered:
09-14-2017

Re: Square root of an 80bit number

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
##

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?

giovanni.meciani

Visitor

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 06:03 AM

2,915 Views

Registered:
09-14-2017

Re: Square root of an 80bit number

Highlighted
##

Jump to solution

drjohnsmith

Teacher

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 06:57 AM

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

<== If this was helpful, please feel free to give Kudos, and close if it answers your question ==>

Highlighted
##

Jump to solution

hpoetzl

Voyager

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 08:08 AM

2,892 Views

Registered:
06-24-2013

Re: Square root of an 80bit number

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
##

Jump to solution

avrumw

Guide

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-05-2017 10:45 AM

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
##

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.

bruce_karaffa

Scholar

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

10-09-2017 07:11 AM

2,812 Views

Registered:
06-21-2017

Re: Square root of an 80bit number