Double Double Division Algorithm

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Subscribe!
@ColinTheMathmo

My latest posts can be found here:
Previous blog posts:
Additionally, some earlier writings:
This page has been Tagged As Education and Tagged As Maths
None of this is new, you can find it on the internet with the appropriate search. I know that.

But having said that, I've never seen it laid out like this, and several people I've shown it to have been surprised by it and found it quite exciting.

For some of my readers, this will all be completely mysterious. But for others, part way through they will go "I recognise this!"

So I'd really like to hear from you ... if you recognise this, at which point did the penny drop? I'd also really like to know if you think this is obvious, and possibly even if you've seen it before.

Note: I don't need it explained to me - I know how it works! But if you'd like to show that you know how it works, then I'd be happy to hear that too.

So ...

Consider the following algorithm. I'll work through an example. I'll divide 450 by 23. We start by creating this table:

A:
.
.
.
.
.
0
B:
23
46
92
184
368
736
C:
.
.
.
.
.
450

The middle row is doubling 23 until the answer is strictly larger than 450. Now suppose we have two columns, using a, b, c for quantities we know, and x and y for quantities we don't (yet) know, we complete the table by working leftwards:

Given this
situation:
A:
x
a
B:
b
2b
C:
y
c

If b >= c then
  • set x = 2a
  • copy c into y
If b < c then
  • set x = 2a+1
  • set y = c-b

Since 368 < 450, the next column is:

2*0+1
A:
.
.
.
.
1
0
B:
23
46
92
184
368
736
C:
.
.
.
.
82
450
450-368

Since 184 >= 82, the next column is:

2*1
A:
.
.
.
2
1
0
B:
23
46
92
184
368
736
C:
.
.
.
82
82
450
Copied

Since 92 >= 82, the next column is:

2*2
A:
.
.
4
2
1
0
B:
23
46
92
184
368
736
C:
.
.
82
82
82
450
Copied

Since 46 < 82, the next column is:

2*4+1
A:
.
9
4
2
1
0
B:
23
46
92
184
368
736
C:
.
36
82
82
82
450
82-46

Since 23 < 36, the next column is:

2*9+1
A:
19
9
4
2
1
0
B:
23
46
92
184
368
736
C:
13
36
82
82
82
450
36-23

So I claim that 450 divided by 23 is 19 with remainder 13.

As I said, for some of you this will feel very familiar. At what stage did you get the connection (with the thing I'm carefully not mentioning)?

Have you seen this before?

Have you thought about this before?

Let me know.


<<<< Prev <<<<
Continuity Concerns
:
>>>> Next >>>>
An Oddity In VIM ...


https://mathstodon.xyz/@ColinTheMathmo You can follow me on Mathstodon.



Of course, you can also
follow me on twitter:

@ColinTheMathmo


Send us a comment ...

You can send us a message here. It doesn't get published, it just sends us an email, and is an easy way to ask any questions, or make any comments, without having to send a separate email. So just fill in the boxes and then

Your name :
Email :
Message :


Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!