14
$\begingroup$

Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in a decimal format, which is limited to very few decimal places, but as an integer instead, while keeping track of the number's precision.

Still, how can a computer simplify computations just like humans do? Take a look at this basic example

$$\sqrt{3} \times (\frac{4}{\sqrt{3}} - \sqrt{3}) = \sqrt{3} \times \frac{4}{\sqrt{3}} - \sqrt{3} \times \sqrt{3} = 4 - 3 = 1$$

That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.

It would surely defeat a human in terms of speed, but it would lack in terms of accuracy. The result will be really close to 1, but not 1 exactly. A computer has no idea that, for instance, $\sqrt{3} \times{\sqrt{3}}$ is equal to $3$. This is only one of the uncountable examples out there.

Did people already find a solution, as it seems elementary for mathematics and computations? If they didn't, is this because it didn't serve any purpose in the real world?

$\endgroup$
8
  • 9
    $\begingroup$ Wolfram Alpha can figure it out $\endgroup$
    – Dan Doel
    Jan 27 at 18:39
  • 20
    $\begingroup$ en.wikipedia.org/wiki/Computer_algebra_system $\endgroup$ Jan 27 at 19:47
  • 12
    $\begingroup$ "a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3" That's where you're wrong: a computer can be clever and manipulate expressions symbolically, just as we do. Computer algebra systems are far more intricate than you give them credit for. $\endgroup$ Jan 27 at 22:03
  • 10
    $\begingroup$ As found and verified by Alan Turing and many others, whatever result a human can obtain with paper, pencil, and rubber, a computer should be able to simulate it. $\endgroup$
    – John L.
    Jan 27 at 22:09
  • 8
    $\begingroup$ Note that computer languages are not, as you state, " limited to very few decimal places". They can all perform or be programmed to perform arbitrary precision arithmetic en.wikipedia.org/wiki/Arbitrary-precision_arithmetic - The other subject you mention is Computer Algebra en.wikipedia.org/wiki/Computer_algebra $\endgroup$ Jan 28 at 14:59
37
$\begingroup$

Sage is an open source computer algebra system. Let's see if it can handle your basic example:

sage: sqrt(3) * (4/sqrt(3) - sqrt(3))
1

What is happening under the hood? Sage is storing everything as a symbolic expression, which it is able to manipulate and simplify using some basic rules.

Here is another example:

sage: 1 + exp(pi*i)
0

So sage can also handle complex numbers.

Computers never handle real numbers, since real numbers cannot be represented exactly on a computer. Instead, they either handle approximate representations of real numbers (usually floating point numbers but sometimes fixed point numbers), or they represent real numbers symbolically, as in the example above. Sage can convert between the two representations (in one direction!), and it can handle floating point numbers of arbitrary accuracy. For example,

sage: RealField(100)(pi^2/6 - sum(1/n^2 for n in range(1,10001)))
0.000099995000166666666333333336072

This computes $\pi^2/6 - \sum_{n=1}^{10^4} 1/n^2$ to 100 bits of accuracy (in the mantissa).

Another approach worth mentioning is interval arithmetic, which is a way of computing expressions with a guaranteed level of accuracy, using provable error brackets. Interval arithmetic is used in computational geometry, together with exact representation of rational numbers.

In theoretical computer science there are several other notions of real computation, but they are mostly of theoretical interest. See the answers to this question.

$\endgroup$
9
  • 6
    $\begingroup$ There are ways of dealing with real numbers on computers, e.g. with Cauchy sequences or Dedekind cuts. But of course, this is not even what people are doing in these examples. They are simplifying symbolic expressions according to rules, just like Sage is. $\endgroup$
    – Dan Doel
    Jan 27 at 21:54
  • 1
    $\begingroup$ What I rarely see discussed is representing a number as a pair (floating point number, best estimate of rounding error). In some cases this will give significantly better results than interval arithmetic. $\endgroup$
    – gnasher729
    Jan 27 at 23:57
  • 4
    $\begingroup$ @gnasher729 This is known as "ball arithmetic". $\endgroup$ Jan 28 at 9:00
  • 2
    $\begingroup$ @DanDoel Aren't Cauchy sequences (and Dedekind cuts) based around infinite structures (sequences or sets)?  So they couldn't be represented directly in a finite computer.  (And if you're not storing them directly, but using some sort of summary or symbolic representation, then what benefit would that have over the ones discussed above?) $\endgroup$
    – gidds
    Jan 28 at 19:52
  • 5
    $\begingroup$ Cauchy sequences (e.g.) are based on functions, and computers can deal with computable functions. The 'advantage' is that this is an actual definition of "the real numbers" (at least, one that would be recognized by a constructivist), and these other structures are not actually the real numbers, but presentations of more tractable subsets of the real numbers. The disadvantage is that many common operations on the real numbers are undecidable in general. I suppose the lesson is that directly using the actual real numbers is not really that important for most people. $\endgroup$
    – Dan Doel
    Jan 28 at 20:16
18
$\begingroup$

Computer algebra is a huge area, probably at least a semester-long university-level course to get most of the basics. However, I think we can cover some of the flavour of it here.

Your case is the easy case, because it is entirely within the language of algebraic numbers (i.e. roots of polynomials), and manipulating polynomials is really the foundation of modern computer algebra. Specifically, you need to understand the concept of a field extension.

A field, you will recall, is an algebraic structure which supports addition, subtraction, multiplication, and division.

Starting with the rational numbers $\mathbb{Q}$, we can extend this with a monomial, which we will call $x$. This gives us the field $\mathbb{Q}[x]$, where the elements of the field are rational polynomials:

$$\frac{p(x)}{q(x)}$$

where $p$ and $q$ are polynomials whose coefficients are rational numbers. We can go further and extend with more monomials, to form, say, $\mathbb{Q}[x][t]$, whose elements are rational polynomials $\frac{p(t)}{q(t)}$ where the coefficients are in $\mathbb{Q}[x]$.

This gives us a language in which we can understand algebraic numbers such as $\sqrt{3}$. It is essentially a field extension with a constraint: $\mathbb{Q}[x]$ subject to the constraint that $x^2 - 3 = 0$.

(NOTE: I'm ignoring the negative solution for the moment, but note that it's not necessary to solve your specific problem! Which solution you use makes a difference when you introduce inequalities. Without knowing that $x > 0$, $\sqrt{3}$ and $-\sqrt{3}$ are surprisingly difficult to tell apart, but that's a tale for another time.)

Technically, this is called an "ideal" rather than a "constraint". And we denote this field as a quotient, $\mathbb{Q}[x] / (x^2-3)$.

Using this machinery, simplifying equations in this form follows a mechanical procedure:

  • Express the equation as an element of the appropriate field extension, applying ideals as you proceed.
  • If the element is a fraction, reduce it using Euclid's greatest common divisor algorithm.

We can start with your equation and express it as a rational polynomial. Perhaps we use a naive method and get something like this:

$$x \times \left(\frac{4}{x} - x \right) = \frac{x}{1} \times \left( \frac {4 - x^2}{x} \right) = \frac{-x^3 + 4x}{x}$$

We can eliminate the $x^3$ by dividing the numerator by $x^2-3$ and taking the remainder. To see why this works, take $x^2 - 3 = 0$ and multiply both sides by $x$, giving $x^3 - 3x = 0$. Add that to the numerator to get:

$$\frac{-x^3 + 4x}{x} = \frac{x}{x}$$

In general, if the ideal has degree $2$, we should be able to reduce any polynomial to a polynomial of degree $1$.

Finally, we can apply Euclid's GCD algorithm to the numerator and denominator to reduce this fraction to $\frac{1}{1}$. And the problem is solved.

EDIT Having said all that, do keep in mind that it's not always obvious what it means to "simplify" a mathematical expression. In some circumstances, a polynomial may be "simpler" if it's expanded and in others, it may be "simpler" if it's factorised.

$\endgroup$
1
  • 2
    $\begingroup$ +1 for the actual walkthrough how it's done. $\endgroup$
    – Stilez
    Jan 29 at 3:22
5
$\begingroup$

Here is your mistake:

That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.

You are assigning a mind to a computer. That's the analog of writing "that's how a gas stove would cook a fish curry". The stove, like the computer, provides mechanisms, like floating point arithmetic. Well, the gas stove actually is better at providing heat than the computer (though it depends on the computer). And either computer or stove certainly come in handy as tools in the process for solving a particular problem. But they are not responsible for the solution.

What is involved here is symbolic computation. You can easily write specific programs for solving particular classes of symbolic computation problems, and there are generic programs for doing that, too. Yes, computers are excellent tools for arriving at numerical solutions, but you can also create numerical solutions using pencil and paper (and many computer arithmetic methods are distilled from pencil-and-paper methods, sometimes after converting to binary arithmetic). Or slide rules.

When a computer produces symbolic output, like a human does when writing down symbols on paper, the scope and meaning of the produced symbols depends on the program that is being used for creating them. Some programs will just produce numerical results (which are easily converted into symbols using digits and a few special characters). Others are intended to produce symbolic results where feasible. Being a computer does not really play a whole lot into it except that humans tend to be a lot better at finding excuses for avoiding calculations (since they are so bad at calculating) and a lot of problems given to humans for practice thus tend to magically have solutions that are simpler than actual real-world problems.

$\endgroup$
2
$\begingroup$

Even for numeric, seemingly obvious computations, computers can struggle: most will have trouble simplifying expressions such as $0.1 + 0.2 - 0.3$.

The following paper gives another way of encoding real numbers, for numeric computations, but without those rounding problems:

Towards an API for the real numbers, H.J. Boehm (2020).

The idea is to represent each number as a function computing its decimal expansion (or a rational approximation with bounded error): common arithmetic operations then just combine those functions into other functions.

It is apparently used in the calculator app on Android phones.

$\endgroup$
3
  • 4
    $\begingroup$ What you're describing is an artefact of a specific binary encoding like IEEE754 that is used for default floating point implementation in most programming languages. But no one doing serious math is gonna be using the default implementation. $\endgroup$
    – Davor
    Jan 28 at 9:23
  • $\begingroup$ Note that this paper is mis-titled. The set of numbers it allows you to perform computation on is the computable numbers (en.wikipedia.org/wiki/Computable_number) which are a countable set of the reals. (there is a bijection between computer programs and countable numbers) $\endgroup$ Jan 30 at 0:57
  • $\begingroup$ I think this answer makes the same error as the question by assigning blame and lack of capability to the computer, and not to the program running on the computer. Try e.g. echo 0.1 + 0.2 - 0.3 | bc -l on your usual Linux system. Sure, one could argue that IEEE floats are more natural to a common processor than decimal numbers, since there is hardware support for floats. But it should be noted that floats aren't decimal numbers, and you're going to have to do something in software to calculate decimals anyway. (Or rationals, which might be more generic.) $\endgroup$
    – ilkkachu
    Jan 30 at 9:21
2
$\begingroup$

First of all, you are mixing different concepts. In your example, you are using algebraic numbers. There algebraic numbers are countably infinite, while real numbers are uncountably infinite.

Generally, for every countably infinite set you can find a data structure that can represent each element of the set (size constraints notwithstanding).

Thus, if you want to simplify expressions of algebraic numbers you can find a way to represent algebraic numbers without loss and then apply a solving algorithm.

√3×√3 is equal to 3. This is only one of the uncountable examples out there.

Again, there are only countably infinite examples. That's why it can work.

For the full set of real numbers, this would not be possible.

$\endgroup$
1
$\begingroup$

You are mistaking a map for the territory.

The first thing to realize is that computers don't work on numbers. Computers work on bits and volts. We abstract that work on volts into working on bits, and we abstract the work on bits to be working on numbers.

Most modern computers use IEEE floating point numbers, not because that is the only thing that they can use, but because IEEE floating point numbers are useful to solve certain kinds of problems. So special purpose hardware to make working with IEEE floating point numbers is added to computers, and they can do calculations using them that are extremely fast.

IEEE floating point numbers represent values as an integer times 2 to the power of another integer, essentially. Both the integer and the power are fixed precision -- they have a max and min size.

When you represent the square root of 3 (or even 0.1) as an IEEE floating point number, you end up with an approximation of the square root of 3. There is some error.

As this error is small, and by design each operation has a reasonably random rounding error at the scales we typically work with, you a likely to get decent approximations of the result of most calculations. But not all calculations.

In other domains, instead of IEEE floating point numbers computers use integers with an upper bound, or integers with no upper bound. These are all common ways to do math on a computer.

There is nothing forcing computers to use IEEE floating point values, or integers, or whatever. Computers are capable of doing symbolic manipulation.

They can represent $x^2=2$ as exactly that -- a string of characters, or tokenize it and turn it into a representation of the algebraic structure. They can do various things we teach high school and undergraduate students to do. They can go through everything you described a "human mathematician" doing to simplify the equation.

They can even do this faster than human mathematicians can do quite often.

This area is called "computer algebra".

In my experience, the hard part is usually explaining the problem to the computer. When you see $x^2=-2$ you probably assume we are working in the reals or the complex numbers, but not the quaternions, constructive reals, $\mathbb{Z}_2$ or something more exotic.

$x^2=2$ in $\mathbb{Z}_2$ means $x=0$. In $\mathbb{R}$ it is unsolvable. In $\mathbb{C}$ it is plus or minus the $i \sqrt{2}$. Etc.

Going further, the constructive reals are a way of axiomitizing real numbers that basically relies on algorithms and proofs.

In it, $\sqrt{2}$ "becomes" a series of values ${v_i}$ and a (provably correct) algorithm that takes any $\epsilon \in \mathbb{Q}$ that is greater than zero, and produces an $N$ such that for all $i>N$, $|v_i^2 - 2| < \epsilon$.

Using this you can produce $\sqrt{2}+\sqrt{3}$ by composing the two series with the algorithm. Even $\sqrt{\frac{2}{3}}$ can be done similarly using nothing but mechanics.

As it happens, $\sqrt{2}-\sqrt{2}=0$ cannot be done as simply; and, in fact, you need to know more about $\sqrt{2}$ than just the series and a black box copy of the algorithm to show that two instances of it when subtracted are zero. In constructive mathematics, equality is not something you get for free, because there is no general way in the real world to prove if two different numbers are equal or not.

The same is true in human mathematics; there are things that are probably provably zero, or equal, we cannot prove are zero.

$\endgroup$
2
  • $\begingroup$ "Computers are capable of doing symbolic manipulation." -- here, too, one could say that computers aren't capable of that. As you just said, they work in bits. Computer programs, on the other hand could well be. I think it's a somewhat important distinction because the question at hand makes the mistake of only looking at what the usual programming language tools allow for, ignoring the possibility of other software allowing something else. $\endgroup$
    – ilkkachu
    Jan 30 at 9:27
  • $\begingroup$ @ilkkachu Imargue that programs are part of computers. They work in volts, or bits, but we arranged thrm to be "Turing Complete", thus what a TM can do (wel, VNM; they are bounded) they can do. $\endgroup$
    – Yakk
    Jan 30 at 13:06
-1
$\begingroup$

Most people use a compiler, which creates operations with floating point numbers (which are not real numbers).

There are specialised tools that will try to manipulate formulas in symbolic form, and they can do exactly what a human can do. You can even do it yourself to sum degree, in any OOP language you can create objects that represent a number as the sum of rational numbers times square roots of integers for example, implement +, -, *, / and you will get exactly what you are asking for.

In principle, question like yours can always be answered by saying "either the designer of the processor adds hardware that does what you want, or some software developer creates software to do it". (Or nobody is bothered doing it, sometimes because it is too difficult, and in some cases it's impossible, but those impossible problems are impossible for humans as well).

$\endgroup$
5
  • 6
    $\begingroup$ There is nothing special about OOP here, you can do the exact same thing in C with structs, or literally any other language with multiple variables per number if they don't support any sort of value grouping (like assembler). $\endgroup$
    – Davor
    Jan 28 at 9:25
  • $\begingroup$ Try redefining + - * / in C. $\endgroup$
    – gnasher729
    Jan 28 at 19:56
  • 3
    $\begingroup$ @gnasher729 It is not necessary to redefine the + - * / operators in C, you just have to parse them in the input stream and provide functions for them. $\endgroup$
    – Glen Yates
    Jan 28 at 23:31
  • 1
    $\begingroup$ @gnasher729 - that has literally nothing to do with it, and it's not recommended to do in C++ either. Operator overloads are evil. $\endgroup$
    – Davor
    Jan 29 at 10:37
  • 1
    $\begingroup$ Also, operator overloading is no way OOP-exclusive technique. $\endgroup$
    – dedObed
    Jan 29 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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