Jump to content


Photo

Challenge: Roots


  • Please log in to reply
21 replies to this topic

#1 FLW_FTW

FLW_FTW

    HACK THE PLANET!

  • Members
  • 59 posts
  • Country:
  • Gender:Male
  • Location:San Francisco

Posted 04 October 2009 - 12:27 AM

There are several ways to calculate the square root of a number. Some of them can be found here: Wikipedia

Calculate the square root of a number n without using any predefined libraries. EG: Don't just submit sqrt( n );

Extra credit: Calculate the root of a number n using only bitwise/logical operations.

Edited by FLW_FTW, 04 October 2009 - 12:30 AM.


#2 intimidat0r

intimidat0r

    SUPR3M3 31337 Mack Daddy P1MP

  • Members
  • 455 posts

Posted 08 October 2009 - 03:29 PM

Spoiler


#3 rainwater_stillicide

rainwater_stillicide

    SUP3R 31337 P1MP

  • Agents of the Revolution
  • 282 posts
  • Location:Scotland

Posted 08 October 2009 - 03:43 PM

I have gotten so much mileage out of this diagram over the years...

The attached image is a Turing machine for finding square roots of integers (the initial tape should contain the argument in unary format):

Attached Files



#4 PurpleJesus

PurpleJesus

    Dangerous free thinker

  • Members
  • 1,578 posts
  • Gender:Male
  • Location:800

Posted 08 October 2009 - 06:33 PM

I have gotten so much mileage out of this diagram over the years...

The attached image is a Turing machine for finding square roots of integers (the initial tape should contain the argument in unary format):


Nice, umm.. could you explain that in terms I might understand? I ain't following what it's supposed to represent.

And I will try this challenge when I'm rested.. Been working long hours lately and can't think too straight.

#5 bcrscahh198987

bcrscahh198987

    Mack Daddy 31337

  • Members
  • 211 posts
  • Location:Ur rektumm

Posted 25 October 2009 - 08:07 AM

In math, they use logarithms to solve roots of any number.
Do you count logarithms as pre-defined libraries?

#6 intimidat0r

intimidat0r

    SUPR3M3 31337 Mack Daddy P1MP

  • Members
  • 455 posts

Posted 27 October 2009 - 07:13 PM

It's trivial to write your own logarithm function anyway.

#7 SwartMumba

SwartMumba

    mad 1337

  • Members
  • 145 posts
  • Gender:Male
  • Location:TX <-- I'm here

Posted 31 October 2009 - 06:56 PM

Here is my method of finding the square root: :rolleyes:
Attached File  sqrRoot.py.txt   1.95KB   27 downloads

Sample output:
= denotes python's sqrt answer
=~ denotes my approximate answer
sqrt(-787) =~ 28.0535714286i
sqrt(289) = 17.0 =~ 17
sqrt(494) = 22.2261107709 =~ 22.2272727273
sqrt(914) = 30.2324329157 =~ 30.2333333333
sqrt(105) = 10.246950766 =~ 10.25
sqrt(796) = 28.2134719593 =~ 28.2142857143
sqrt(998) = 31.5911379979 =~ 31.59375
sqrt(701) = 26.4764045897 =~ 26.4807692308
sqrt(704) = 26.5329983228 =~ 26.537037037
sqrt(108) = 10.3923048454 =~ 10.4
sqrt(336) = 18.3303027798 =~ 18.3333333333
sqrt(167) = 12.9228479833 =~ 12.9230769231
sqrt(906) = 30.0998338866 =~ 30.1
sqrt(133) = 11.5325625947 =~ 11.5416666667
sqrt(304) = 17.4355957742 =~ 17.4411764706
sqrt(535) = 23.1300670124 =~ 23.1304347826
sqrt(947) = 30.7733651069 =~ 30.7741935484
sqrt(262) = 16.1864140562 =~ 16.1875
sqrt(950) = 30.8220700148 =~ 30.8225806452
sqrt(323) = 17.9722007556 =~ 17.9722222222
sqrt(454) = 21.3072757527 =~ 21.3095238095

Edited by SwartMumba, 31 October 2009 - 07:58 PM.


#8 SwartMumba

SwartMumba

    mad 1337

  • Members
  • 145 posts
  • Gender:Male
  • Location:TX <-- I'm here

Posted 03 November 2009 - 01:46 AM

I am disappointed no one looked at what I did. :sad:

#9 bcrscahh198987

bcrscahh198987

    Mack Daddy 31337

  • Members
  • 211 posts
  • Location:Ur rektumm

Posted 13 November 2009 - 05:07 AM

I am disappointed no one looked at what I did. :sad:


It's very interesting if I could understand it.


edit::: oh, and by the way. I checked with my TI-84. It seems python's native square root is much more accurate.

edit::: And whats "f'(B)(x-B)"?? inverse function?



I added comments to your code, check the comments.

Let x equal the value you want to find the square root of.
	Let b be a value near x, which you know the square root of.
	Let f(x) = (x)^0.5
	then,g(x) = f(<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' /> + f'(<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />(x-<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />  # By the way smartmumba, f' is inverse function?
	in my code, a = sqrt(<img src='http://www.binrev.com/forums/public/style_emoticons/<#EMO_DIR#>/cool.gif' class='bbc_emoticon' alt='B)' />'''


Those damn smileys, for the first time, I finally understood why boards have disable smileys option. Except this board doesn't have it.

Edited by bcrscahh198987, 13 November 2009 - 05:21 AM.


#10 intimidat0r

intimidat0r

    SUPR3M3 31337 Mack Daddy P1MP

  • Members
  • 455 posts

Posted 14 November 2009 - 03:05 PM

edit::: And whats "f'(B)(x-B)"?? inverse function?


That would be the derivative of f times (x-B).

#11 bcrscahh198987

bcrscahh198987

    Mack Daddy 31337

  • Members
  • 211 posts
  • Location:Ur rektumm

Posted 27 November 2009 - 02:29 PM

I got a simple but inefficient method of doing it.

How do you find the square root of a number by hand?
What about cube roots?

The square root of a number is just the number which when multiplied by itself gives the first number. So 2 is the square root of 4 because 2 * 2 = 4.

Start with the number you want to find the square root of. Let's use 12. There are three steps:

Guess
Divide
Average.
... and then just keep repeating steps 2 and 3.

First, start by guessing a square root value. It helps if your guess is a good one but it will work even if it is a terrible guess. We will guess that 2 is the square root of 12.

In step two, we divide 12 by our guess of 2 and we get 6.

In step three, we average 6 and 2: (6+2)/2 = 4

Now we repeat step two with the new guess of 4. So 12/4 = 3

Now average 4 and 3: (4+3)/2 = 3.5

Repeat step two: 12/3.5 = 3.43

Average: (3.5 + 3.43)/2 = 3.465

We could keep going forever, getting a better and better approximation but let's stop here to see how we are doing.

3.465 * 3.465 = 12.006225

That is quite close to 12, so we are doing pretty well.

http://mathforum.org...rt.by.hand.html

http://mathforum.org...rt.by.hand.html



That's probably the simplest way to do it, the problem would probably be how many times are you going to loop or repeat the steps until you feel it's correct. The bigger the number you want to calculate for, you'll want to use more loops.

The second problem , that I can think of, is the part with guessing. How are you going to guess? If you try to find the root of 1, how is the computer going to guess properly?

Edited by bcrscahh198987, 27 November 2009 - 03:10 PM.


#12 bcrscahh198987

bcrscahh198987

    Mack Daddy 31337

  • Members
  • 211 posts
  • Location:Ur rektumm

Posted 27 November 2009 - 03:17 PM

Anyway, here's my method in ruby

Spoiler



here's my sample output
494 ~= 22.61107708929
914 ~= 30.2324329156619


This means I can make my answers as accurate as I want it by adjusting the amount of times of the loop.

In this case it's 15 times.


and by the way, my answers are much more accurate than SwartMumba. haha :)

Edited by bcrscahh198987, 27 November 2009 - 03:35 PM.


#13 bcrscahh198987

bcrscahh198987

    Mack Daddy 31337

  • Members
  • 211 posts
  • Location:Ur rektumm

Posted 27 November 2009 - 03:30 PM

So there's 3 methods so far.



Fast inverse square,

Linearization

Averaging.





Any other approach?

#14 bcrscahh198987

bcrscahh198987

    Mack Daddy 31337

  • Members
  • 211 posts
  • Location:Ur rektumm

Posted 27 November 2009 - 03:37 PM



edit::: And whats "f'(B)(x-B)"?? inverse function?


That would be the derivative of f times (x-B).



Using derivatives huh? I'm not in calculus yet. I only understand it to be slope of a curve or tangent to the curve.

Oh yeah, How do I get rid of those smileys??

Edited by bcrscahh198987, 27 November 2009 - 03:38 PM.


#15 zandi

zandi

    SUP3R 31337 P1MP

  • Members
  • 263 posts
  • Location:michigan

Posted 17 December 2009 - 12:10 AM

oooh, this should be a fun challenge. i'll finally be able to apply what i've learned in calc II in a real world situation.

i'll work on this and submit my code later, but my general strategy will be:
Spoiler


also swartmumba, i'm wondering why your sqrt() function is giving a result for a negative input without using imaginary numbers, hehe.

#16 SwartMumba

SwartMumba

    mad 1337

  • Members
  • 145 posts
  • Gender:Male
  • Location:TX <-- I'm here

Posted 17 December 2009 - 07:26 PM

oooh, this should be a fun challenge. i'll finally be able to apply what i've learned in calc II in a real world situation.

i'll work on this and submit my code later, but my general strategy will be:

Spoiler


also swartmumba, i'm wondering why your sqrt() function is giving a result for a negative input without using imaginary numbers, hehe.


There is an imaginary number!
Look at the end.
sqrt(-787) =~ 28.0535714286i <-- see i

#17 zandi

zandi

    SUP3R 31337 P1MP

  • Members
  • 263 posts
  • Location:michigan

Posted 17 December 2009 - 09:20 PM

ah, didn't notice that. i suppose it's alright then.

#18 zandi

zandi

    SUP3R 31337 P1MP

  • Members
  • 263 posts
  • Location:michigan

Posted 20 December 2009 - 09:43 PM

alright, i think i've got it:

Spoiler


as far as i've checked, it's as accurate as sqrt(), though i haven't bothered to code for negative input.

#19 SwartMumba

SwartMumba

    mad 1337

  • Members
  • 145 posts
  • Gender:Male
  • Location:TX <-- I'm here

Posted 25 December 2009 - 11:23 PM

Nice Zandi.

I think it was in MITs calc HW questions - or maybe Calculus Early Transcendentals - that I read some computers use this method to calculate the square root.

+1

Edited by SwartMumba, 25 December 2009 - 11:24 PM.


#20 zandi

zandi

    SUP3R 31337 P1MP

  • Members
  • 263 posts
  • Location:michigan

Posted 26 December 2009 - 12:26 PM

Nice Zandi.

I think it was in MITs calc HW questions - or maybe Calculus Early Transcendentals - that I read some computers use this method to calculate the square root.

+1


thanks. the nice part about the series is that for the range it converges, you know it is exactly equal to the function. the problem is with computers you can't calculate an infinite sum, just find an approximation, so you have to hope it converges quickly enough. in this case it did, but i'm sure for other functions this approach wouldn't work so well.




BinRev is hosted by the great people at Lunarpages!