42
votes
\$\begingroup\$

Hi guys, for my class I need to make a number square root but it doesnt work !!HELLPP!

The challenge:

Write a function or program that will "make a number square root". 

Note: This is code trolling. Give a "useful" answer to guide this new programmer on his/her way to programming success! Be creative!

\$\endgroup\$

closed as too broad by copy, Konrad Borowski, squeamish ossifrage, Justin, Doorknob May 10 '14 at 3:19

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

locked by Doorknob May 11 '14 at 23:07

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

  • 63
    \$\begingroup\$ @CloseVoters Please stop voting to close [code-trolling] as off topic because of lack of winning criteria. In this case, this is obviously a [popularity-contest]. Edit it in if you want to. Just because you don't like [code-trolling] doesn't mean that you have to close the challenge for everyone else. Obviously, many people like this type of challenge, evidenced by the number of answers, so, since SE is a community-driven site, leave it open for these people. \$\endgroup\$ – Justin Apr 21 '14 at 8:01
  • 12
    \$\begingroup\$ @Quincunx For the record, my vote was for Too Broad. There's literally nothing to go by except "make something related to square roots." (As evidenced by there being fifteen answers already.) \$\endgroup\$ – Doorknob Apr 21 '14 at 11:57
  • 7
    \$\begingroup\$ Close-voters: Can you help me understand how this is any more "broad" than other unclosed [code-trolling] questions? Maybe there's a valid close reason here, but the code-trolling category is naturally going to be a bit broader than most challenges. Otherwise, it would somewhat defeat the purpose. \$\endgroup\$ – Geobits Apr 21 '14 at 13:18
  • 6
    \$\begingroup\$ @Geobits, by saying that the answer doesn't even have to be correct, this is as broad as "Write some code". \$\endgroup\$ – Peter Taylor Apr 21 '14 at 13:54
  • 11
    \$\begingroup\$ @Gareth It's an interesting analogy, but it doesn't match the original comment. You're most welcome to stand outside McDonalds all day with a banner telling people the food is crap. And you are most welcome to downvote/put negative comments on this question. However if you try to physically stop people from entering McDonalds (the equivalent of the second round of close voting, which has just begun) you'll most likely get arrested. I've some sympathy with the anti code-trolling cause and I will not be upvoting (or downvoting) this question. But I want freedom to post an answer if I have one. \$\endgroup\$ – Level River St Apr 21 '14 at 15:44

41 Answers 41

2
votes
\$\begingroup\$

Fortran 90+

Obviously logarithms and decimal powers are significantly faster than using the intrinsic square-root function, so we use that.

For any x^n, it is always true that log(x^n,b)=n.log(x,b) where b is the base. For simplicity, we use b=10:

program find_square_root
   implicit none
   integer, parameter :: wp = kind(1d0)
   real(wp) :: x, logx, alogx

! infinite loop
   do
      print *,"What is value: "
      read(*,*) x
      if(x < 0) exit
      logx=0.5_wp*log(x)/log(10_wp)
      alogx=10_wp**(logx)
      print *,"square root = ",alogx
   enddo
   print *,"thank you"
end program find_square_root

which will keep running until you type a negative value for an input.

There really isn't any trick here, just that taking logarithms and powers is slow.

\$\endgroup\$
2
votes
\$\begingroup\$

Python 2 This does it. It only round values to integers.

number=raw_input("Number? ")
if float(number)<0: exit("Not defined")
else:               number=int(float(number)+0.5)
if number<2:        exit("1")
elif number<5:      exit("2")
c=1
while True:
    c+=1
    if c**2 < number:   continue
    exit(str(int((c-1)*(c))/2))
\$\endgroup\$
2
votes
\$\begingroup\$

TI-BASIC

Roots are usually squiggly. Let's make them square for a change. Just enter the size and watch plants grow on your calculator!

:Input A:A
:While Ans
:Ans-1
:Output(Ans,1,A
:End
\$\endgroup\$
  • 1
    \$\begingroup\$ Looks interesting, what does it do exactly? \$\endgroup\$ – reggaemuffin Apr 25 '14 at 0:21
  • \$\begingroup\$ @Kostronor Outputs squares in the text console of a certain size. \$\endgroup\$ – Timtech Apr 25 '14 at 10:48
2
votes
\$\begingroup\$

jQuery

This actually uses jQuery to do entire calculation. It creates a set of tags in a container (equal to the requested number), changes the width until it will be identical to height. When square root is reached, those numbers should be identical (if you have 8x8 grid, you have 64 elements, and the square root of 64 is 8). Who needs plain JavaScript, when you have jQuery, and jQuery is awesome!

function squareRoot(number) {
    // overflow: hidden is needed so the element would report real size.
    var $calculator = $('<div>').css('overflow', 'hidden');
    var i;
    var result = NaN;
    for (i = 0; i < number; i++) {
        // Floats are the easiest way to put elements that only take
        // place for themselves.
        $calculator.append($('<div>').css('float', 'left').height(1).width(1));
    }
    // The element needs to exist in document to calcualte its width.
    $('body').append($calculator);

    try {
        // Bruteforce the solution
        for (i = 1; i <= number; i++) {
            $calculator.width(i);
            if (i === $calculator.height()) {
                return i;
            }
        }
    }
    finally {
        // Clean the element after calculation. There is no need for
        // garbage to exist after calculation.
        $calculator.remove();
    }
}
\$\endgroup\$
2
votes
\$\begingroup\$

JavaScript (also works in ActionScript)

function sqrt(num) {
    var k = 0;
    while (k * k != num)
        { k = Math.random() * num; }
    return k;
}

The troll:

It just keeps looping through, creating random values less than num, until it finds a value that fits the bill. May break if num <= 1.

\$\endgroup\$
  • \$\begingroup\$ I think you should change the while condition to k * k = num. \$\endgroup\$ – Paŭlo Ebermann Apr 26 '14 at 17:57
  • \$\begingroup\$ @PaŭloEbermann Good idea, and that's also more efficient! I implemented your suggested changes. \$\endgroup\$ – IQAndreas Apr 26 '14 at 23:19
1
vote
\$\begingroup\$

Everybody's got this all wrong. This is the only valid solution (I'll use Python):

def getSqrt(int num):
    return 42

getSqrt(1764)

When running this code, the function clearly returns 42.

As it turns out, when running the code,

getSqrt(6*9)

It also returns 42. Maybe Hitchhikers got it wrong. Its not 6*9=42, it is the square root of 6*9 equals 42.

\$\endgroup\$
0
votes
\$\begingroup\$

Python

import math
print math.sqrt(input())
\$\endgroup\$
  • 6
    \$\begingroup\$ This is code-trolling. Your answer does not seem very trollish. \$\endgroup\$ – ace Apr 22 '14 at 7:18
  • 2
    \$\begingroup\$ @ace - i'm trolling the question by giving a correct answer \$\endgroup\$ – TheDoctor Apr 22 '14 at 14:07
  • 10
    \$\begingroup\$ And voters are trolling you by giving you a downvote. \$\endgroup\$ – ace Apr 22 '14 at 15:11
  • \$\begingroup\$ The troll is that it evals an user specified value, is it? \$\endgroup\$ – Konrad Borowski Apr 26 '14 at 15:29
0
votes
\$\begingroup\$

Python

This is the only answer that will terminate with an inexact answer. Time is no object when it comes to being precise!

import sys
from decimal import *
two = Decimal('2')
half = Decimal('0.5')
context=getcontext()
prec = 5
sys.stdout.write('1.414')
while True:
    prec += 1
    context.prec = prec
    sys.stdout.write(str(two**half)[-2])
\$\endgroup\$
0
votes
\$\begingroup\$

Haskell

Just as we can define recursively Fibonacci sequence

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

we can use generalized continued fractions to express a fraction that converges to the square root with ultimate precision:

import Prelude hiding (sqrt)

sqrt :: Double -> Double
sqrt x = 1 + (x - 1) / cfrac
  where cfrac = 2 + (x - 1) / cfrac

Simple and elegant.

While the continued fraction converges, the program does not. We'd have to limit the number of recursive nesting in order to get a result.

\$\endgroup\$
0
votes
\$\begingroup\$

Java (in a custom number class)

Once I did develop an implementation of arbitrary large natural numbers (= nonnegative integers) in a decimal system.

It also contained a square root method.

/**
 * Berechnet näherungsweise die Quadratwurzel dieser Zahl.<p>
 * <b>Implementation:</b>
 * Dabei wird für mehr-als-2-stellige Zahlen das
 *   Divisionsverfahren angewandt.
 * @return die größte natürliche Zahl, dessen Quadrat kleiner
 *   oder gleich dieser Zahl ist. Bei <pre>
 *  Zahl qw = Z.quadratWurzel();
 * </pre> gilt: <pre>
 *  qw * qw <= Z < (qw + 1) * (qw + 1)
 * </pre>
 * @since PPS 1.1.3
 */
public Zahl quadratWurzel()
{
    DebugMessage.print(this + ".quadratWurzel()");
    DebugMessage.begin();

    // triviale Fälle:

    if (qwurzel != null)
        return qwurzel;

    if (1 == len)
        {
            DebugMessage.end();
            return qwurzel = valueOf(zifs[start].quadratWurzel());
        }
    if (2 == len)
        {
            for (Zahl z = NEUN; ! z.equals(NULL) ; z = z.getVorgänger())
                {
                    if (z.mal(z).compareTo(this) <= 0)      // z² <= this ?
                        {
                            DebugMessage.end();
                            return qwurzel = z;
                        }
                }
        }

    int ix =
        ((len & 1) == 0) ?
        len - 2 :
        len - 1;
    int restLen = len;

    // hier kommt das Ergebnis hinein:
    Ziffer[] wuZifs = new Ziffer[(len+1)/2];        // nur halb so viele Ziffern!
    int wuIx = wuZifs.length - 1;

    Zahl anfang = valueOf(this, ix);        // höchstens 2 Ziffern
    DebugMessage.print("anfang = " + anfang);
    Zahl a = anfang.quadratWurzel();        // "=> höchstens 1 Ziffer!
    anfang = a.mal(a);                      // a²
    DebugMessage.print("anfang = " + anfang);
    wuZifs[wuIx] = a.getZiffer(0);

    Zahl rest = this.minus(anfang.shl(wuIx * 2));

    while (--ix > 0)
        {
            DebugMessage.begin("while-Schleife-Körper ...");
            DebugMessage.print("rest = " + rest + ", ix = " + ix);
            DebugMessage.print("wuZifs = " + JavaTools.ar2Str(wuZifs) +
                               ", wuIx = " + wuIx);
            Zahl ergBisher = valueOf(wuIx, wuZifs.length - wuIx, wuZifs);
            DebugMessage.print("ergBisher = " + ergBisher);
            Zahl restTeil = valueOf(rest, ix);
            DebugMessage.print("restTeil = " + restTeil);
            Zahl divisor = ergBisher.mal(ZWEI);
            DebugMessage.print("divisor = " + divisor);
            Zahl nextZif = restTeil.intDurch(divisor);
            DebugMessage.print("nextZif = " + nextZif);
            ix --; wuIx --;
            DebugMessage.print("ix = " + ix + ", wuIx = " + wuIx);
            wuZifs[wuIx] = nextZif.getZiffer(0);
            DebugMessage.print("wuZifs = " + JavaTools.ar2Str(wuZifs));
            Zahl subtr = divisor.mal(ZEHN).plus(nextZif).mal(nextZif).shl(wuIx * 2);
            DebugMessage.print("subtr = " + subtr);
            while (subtr.compareTo(rest) > 0)
                {
                    nextZif = nextZif.getVorgänger();
                    DebugMessage.print("nextZif = " + nextZif);
                    wuZifs[wuIx] = nextZif.getZiffer(0);
                    DebugMessage.print("wuZifs = " + JavaTools.ar2Str(wuZifs));
                    subtr = (divisor.shl(1).plus(nextZif)).mal(nextZif).shl(ix);
                    DebugMessage.print("subtr = " + subtr);
                }
            rest = rest.minus(subtr);
            DebugMessage.end("Ende while-Schleife-Körper");
        }
    Zahl erg = new Zahl (0, wuZifs.length, wuZifs);
    DebugMessage.end();
    return qwurzel = erg;
}

The whole method works as specified: Z.quadratWurzel() returned a natural number qw such that qw * qw <= Z < (qw + 1) * (qw + 1), i.e. qw = ceil(sqrt(Z)).

I won't post the whole Zahl class here, just an outline:

  • a Zahl (german for "number") consists of an array of (decimal) digits (Ziffer) and an offset + length into it (the idea copied from the String class).
  • All of the basic and some not-so-basic methods were implemented, based on methods of the Ziffer class, and with algorithms just like humans would do the arithmetic on paper or in their heads (or at least how I learned them in elementary school.)
  • There even was a prime factorization algorithm in there (based on a way I was using in my head to factor around 4-digit numbers – a variant of trial division, I suppose.)

I actually never did learn any square root algorithm in school, but I found a description in the notes of my sister, whose math teacher did instruct this algorithm (10th grade or similar, I think), and implemented it here. I think it is a specialization (for n=2) of the algorithm explained at Wikipedia's Shifting nth root algorithm article.

Some hints for understanding the code:

  • quadratWurzel is german for square root.
  • The DebugMessage class is used just for debugging goals – I could plug several implementations, one which printed to the console or a file and changed indentation levels with begin() and end(), another one filling a Swing JTree with the messages. You should be able to ignore it (or try translating the messages to use it as comments). JavaTools.ar2Str was an array-to-string formatting function I wrote before there was Arrays.toString(). Of course both Zahl and Ziffer have a useful toString() method.
  • zifs is the array of digits (which might be shared with other Zahl instances), len is the number of digits used by our number, start is the offset in this array where our digits start. The digits are sorted in little-endian way in the array. getZiffer() is a method accessing one of the digits.
  • We see use of most basic operations (implementation not included, but you can replace them by operations on primitives ints):
    • plus means "plus", this is the addition method. Replace a.plus(b) by a + b.
    • minus means "minus", this is the subtraction method. Replace a.minus(b) by a - b.
    • mal means "times", this is the multiplication method. Replace a.mal(b) by a * b.
    • intDurch() is integer division (ignoring the remainder). Replace a.intDurch(b) by a / b. (There is another division method which throws an exception if it is not dividable.)
    • "Vorgänger" means "predecessor", so z = z.getVorgänger(); would z--; with ordinary primitive types.
    • shl = shift left is shifting the number left by some number of (decimal) digits, effectively appending zero digits at the end, or multiplying with a power of ten.
    • Zahl.valueOf(Zahl, int start) is one of several factory methods. This one works like a substring-like function, cutting away the lowest-value start digits. This effectively divided by 10^start, discarding the remainder.
  • We have some special-casing for one- and two-digit numbers.
    • NULL, EINS, ZWEI, ... to NEUN, ZEHN are constants for the numbers zero to ten.
  • there is some recursion, but only for the first one or two digits (which are special-cased anyways), to get started.
  • We use the wuZifs array to collect the result digits.
  • I don't really understand anymore what is going on in the main loop, all that debug output is obfuscating what happens, and I'm too tired. Read the Wikipedia article for details.
  • We are caching the value in the qwurzel field to avoid calculating it more than once for a given number instance.
  • erg is short for "Ergebnis", the result.

! If I now found that kind of code anywhere near a production environment, I would consider sending it to TheDailyWTF. Luckily I know it never was used for any goals other than my own learnings. And even those were more than ten years ago, I think even around fifteen.

! See Creating a simple Big number class in Java for a later attempt at a more sane implementation of "big decimal-based integers, though I didn't implement square roots there.

\$\endgroup\$
  • \$\begingroup\$ Is the troll that most users cannot understand your comments or variable names? \$\endgroup\$ – erdekhayser Apr 29 '14 at 2:04
0
votes
\$\begingroup\$

Python 2.7

I quake in the presence of my betters. Their answers are incredible. However, I feel your learning will be incomplete if you do not see an algorithmic implementation of a square root method so simple that people have used it by hand. Wikipedia explains this algorithm.

I have provided the following Python code as a sample implementation of the algorithm. While Python is slower than Java (which is slower than ASM, which is slower than C), I have found that this is because the computer is being more careful with its calculations. Combining this with Python's great readability, I believe you should use Python for every homework assignment. If your professor tells you to use a different language, explain to him why he is wrong.

Here is this alternative square root approach:

def sqrt(z):
 v,w,y=10,0,100
 def A(x):
    a,b=D(x),[];c=x-a
    while a>w:b.insert(w,a%y);a//=y
    b.append(None)
    while c>w:c*=y;x=D(c);b.append(x);c-=x
    return b
 B=lambda x:reduce(lambda x,y:x if y is None else x*v+y,x,w)
 C=lambda x,y:(x+y)*y
 D=int
 a,b,c,d= w,[],-1,A(z);e=len(d);f=e+y
 while c+1<f and(c<e or a>w):
    c += 1
    if c<len(d) and d[c]is None:b.append(None);continue
    a*=y
    if c<e:a+=d[c]
    g=B(b)*20;h=max(filter(lambda c:C(g,c)<=a,range(v)));b.append(h);a-=C(g,h)
 return float(''.join(map(lambda x:'.' if x is None else str(x),b)))

Here are some results showing what it produces:

Python 2.7.6 (default, Nov 10 2013, 19:24:24) [MSC v.1500 64 bit (AMD64)] on win
32
Type "help", "copyright", "credits" or "license" for more information.
> > from random import *
> > from golfedSqrt import sqrt
> > digits = [i for i in range(11)]
> > digits.extend([random() * 1e9 + random() for i in range(10)])
> > for d in digits:
...     print "{} => {}".format(d, sqrt(d))
...
0 => 0.0
1 => 1.0
2 => 1.41421356237
3 => 1.73205080757
4 => 2.0
5 => 2.2360679775
6 => 2.44948974278
7 => 2.64575131106
8 => 2.82842712475
9 => 3.0
10 => 3.16227766017
216308371.652 => 14707.4257317
556847164.007 => 23597.6092858
106003255.816 => 10295.7882562
824923809.742 => 28721.4868999
204798557.219 => 14310.7846472
742647120.414 => 27251.5526239
199156541.747 => 14112.283364
788130088.331 => 28073.6547021
525449922.652 => 22922.6944893
529451788.497 => 23009.819393
> >

I believe the virtues of this approach are self-evident thanks to Python's strengths.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.