Newtons Square Root Method in Racket

Isaac Newton came up with an elegant method for calculating square roots through a series of approximations that get refined over time. At the end of this post, I will show a racket implementation of the procedure.

Overview

The square of \(x\) can be written as either \(2*2\) or in the exponential form \(x^2\). Therefore, the square of 2 is 4 because \(2*2\) is 4 and the square of 3 is 9 because \(3 * 3\) is 9. It’s called squaring because when you multiply a number by itself, you form the area of a square since the two numbers are the same and can be conceptualized as equal sides on a square.

Square roots are the inverse of squares and the square root of x can be written in its fractional exponential form \(x ^ {1/2}\) or more commonly \(\sqrt{x}\). If \(\sqrt{x} = y\), then it must also follow that \(y^2 = x\).

A perfect square is a number that is the product of a number multiplied by itself. Some examples of perfect squares are 4 (\(2*2\)), 9 (\(3*3\)), 16 (\(4*4\)), and 25 (\(5*5\)).

Finding the square root by … guessing

What’s the square root of 9? How do you compute this in your head if you don’t already know that the answer is 3?

Start guessing!

Pick a number less than 9 and square it and see how close I get to 9. If the answer is less than 9, then the square root must be larger than my current guess. And if it’s larger than 9, then the square root is smaller than my current guess.

There’s two parts to this process:

  1. Guessing a number that represents the square root
  2. Checking whether the square if the guess is within the threshold of what we are looking for (as close to 0 as possible)

To phrase this more precisely, given \(\sqrt{x}\), we’re looking for \(y\) such that \(x – y ^ 2 = 0\).

A closer look at newtons method

\(let\ a = 9\), where 9 is the number we’re trying to find square root for. Think of it as the total area of a rectangle.

\(x\) is our guess.

\(y\) is the other side of our rectangle such as \(x*y = a\)

Think of 9 as an area of a rectangle. You can form it in different ways / different dimensions but with the same area. The last shape is a perfect square with equal sides – the side of a perfect square is what we’re looking for.

Given any \(x\) and \(y\) such that \(x * y = a\), we know that any other value less than \(x\) if \(y\) is unchanged will be < \(a\) and any value more than \(y\) will be > \(a\).

To make a better guess towards a value that brings us closer to the perfect square such that \(x * y = a\) and \(x = y\), \(x\) needs to be bigger and \(y\) needs to be smaller.

Basically, we want \(x\) to be as close to \(y\) as possible, so they need to get closer over time in order for us to find the answer. Therefore, a better guess needs to be a value that is between \(x\) and \(y\).

One such better guess is the average of \(x\) and \(y\)!

By repeating this process, we converge on the answer.

Racket Implementation

#lang racket

(define (sqrt x)
    (define (square x) (* x x))

    (define (good-enough? guess x)
      (< (abs (- (square guess) x)) 0.001))

    (define (average x y) (/ (+ x y) 2))

    (define (improve guess x)
      (average guess (/ x guess)))

    (define (sqrt-iter guess x)
      (if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

    (sqrt-iter 1.0 x)
)

SICP Exercise 1.5 – Testing Evaluation Order

Prompt

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation.

To refresh your memory, “applicative-order” means that procedure arguments get evaluated before being substituted into a procedure. “Normal-order” means that procedure arguments get evaluated later and only if needed (lazy).

He defines the following two procedures:

(define (p) (p))

(define (test x y) 
  (if (= x 0) 
      0 
      y))

The first procedure is a function by the name p that returns the invocation of itself. So it’s a recursive call. The second procedure performs a conditional check on two variables. If x is zero, return zero. Otherwise return y.

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation?

Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Solution

Consider applicative order first where arguments are evaluated first before being passed into the function.

Given (test 0 (p)), the arguments are 0 and (p).

0 is a literal primitive so it just evaluates to itself (zero).

(p) is a procedure application (a procedure that accepts no arguments) that returns the result of another procedure application (the application of itself, p). Since it’s an application that returns the application of itself with no terminating condition, it’ll continue applying itself indefinitely! In other words, we’ll never actually get a chance to enter into the test procedure call due to this non-terminating procedure.

On the other hand, with normal order evaluation where the arguments are evaluated on when needed, (test 0 (p)) will expand to (if (= 0 0) 0 (p)).

Since the condition is true, and given that the if special form never evaluates the right hand side expression unless the condition is false, the return value is 0. If we changed our procedure application to (test 1 (p)) however, it’ll enter into an infinite loop.

Takeaway

This small example demonstrates a fairly deep idea. Given the same arguments to a function and applying the substitution model of reasoning about how symbols get replaced with values, evaluation order matters. This is not an obvious concept and one that surprised me even though I’ve been programming for many years.

If most languages you’ve used implement applicative order evaluation, code that looks like should exhibit the same behavior in a language that uses normal order evaluation would be surprising.

What are the pros and cons of normal order evaluation?

Are there any programming languages that use normal order evaluation?

How do you implement normal order evaluation in an interpreter?

What’s the difference between controlled and uncontrolled inputs in ReactJS?

Uncontrolled inputs are input elements that have their state stored strictly in the browser document object model (DOM). They behave like vanilla HTML inputs that you create without using a framework like React.

Uncontrolled (out of control? lol) inputs

There’s a couple of ways you can create uncontrolled inputs.

The first is to leave out the value attribute of an input.

function App() {
  return (
    <div>
      <input type="text" name="title"/>
    </div>
  );
}

This input behaves like a regular input. But if you need to access the value of this input inside your component – say, to submit the form or to do some other processing with the value – then you can’t access it without directly accessing the value from the DOM itself using the DOM API (i.e document.getElementsByTagName).

If you’re using ReactJS in the first place, you’re probably trying to avoid having to work directly with the DOM API. Now there are situations when you do want to read DOM state directly and React offers a way to do that with uncontrolled inputs through its own API called refs.

Here’s an example of reading state from our uncontrolled component with refs:

App() {
  const inputRef = useRef(null);
  const handleClick = () => {
    alert(inputRef.current.value);
  };
  return (
    <div>
      <input type="text" name="title" ref={inputRef} />
      <button onClick={handleClick}>Click</button>
    </div>
  );
}

We bind the input to a ref object that’s created using the useRef hook. This creates a connection to our input element and allows us to access the DOM value directly without having to use the DOM API. In most situations where you want or need to use uncontrolled inputs, refs are the way to go.

You can also create an uncontrolled input by setting a value attribute – but only if the value is null or undefined.

Here’s an example with undefined

function App() {
  return (
    <div>
      <input type="text" name="title" value={undefined} />
    </div>
  );
}

This behaves just like an input that doesn’t have a value attribute at all.

Controlled inputs

Controlled inputs that get their value from React component state rather than from the DOM. The component is the source of truth for the value of the input.

For example

function App() {
  const [title, setTitle] = useState("dog day afternoon");
  return (
    <div>
      <input type="text" name="title" value={title} />
    </div>
  );
}

If you tried to type into this input, the value won’t actually change! That’s because nothing in the component is currently writing to the title variable. That’s why most controlled inputs will come with change handlers.

function App() {
  const [title, setTitle] = useState("dog day afternoon");
  return (
    <div>
      <input type="text" name="title" value={title} onChange={(e) => setTitle(e.target.value) }/>
    </div>
  );
}

Danger! Changing a controlled input to an uncontrolled input between renders

Now that we’ve covered the difference between a controlled and uncontrolled component – what happens if this same input element changes from a controlled element to an uncontrolled one?

To demonstrate what happens, lets add a toggle handler that toggles the title state between a string value and undefined.

function App() {
  const [title, setTitle] = useState("dog day afternoon");
  const toggleTitle = () => {
    if (title) {
      setTitle(undefined);
    } else {
      setTitle("dog day afternoon");
    }
  }
  return (
    <div>
      <input type="text" name="title" value={title} onChange={(e) => setTitle(e.target.value) }/>
      <button onClick={toggleTitle}>Toggle</button>
    </div>
  );
}

Clicking toggle produces the following error

Warning: A component is changing a controlled input to be uncontrolled. This is likely caused by the value changing from a defined to undefined, which should not happen. Decide between using a controlled or uncontrolled input element for the lifetime of the component. More info: https://reactjs.org/link/controlled-components

In most cases, you can fix this by ensuring that you don’t supply undefined or null to your inputs. You can do this with some additional data processing or validation before that value is bound to the input at render time.