mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

Off-by-one errors

 2022-12-29 
This is the 100th blog post on this website!
But if I hadn't pointed this out, you might not have noticed: the URL of the page is mscroggs.co.uk/blog/99 and not mscroggs.co.uk/blog/100. This is a great example of an off-by-one error.
Off-by-one errors are one of the most common errors made when programming and elsewhere, and this is an excellent opportunity to blog about them.

Fence posts and fence panels

Imagine you want to make a straight fence that is 50m long. Each fencing panel is 2m long. How many fence posts will you need?
Have a quick think about this before reading on.
If you're currently thinking about the number 25, then you've just made an off-by-one error. The easiest way to see why is to think about some shorter fences.
If you want to make a fence that's 2m long, then you'll need just one fence panel. But one fence post will not be enough: you'll need a second post to put at the other end of the fence panel.
If you want to make a 4m long fence, you'll need a post before the first panel, a post between the two panels, and a post after the second panel: that's three posts in total.
In general, you'll always need one more fence post than panel, as you need a fence post at the start of each panel and an extra post at the end of the final panel. (Unless, of course, you're building a fence that is a closed loop.)
This fence has 4 fence panels but 5 fence posts
This fence post/fence panel issue appears surprisingly often, and can make counting things quite difficult. For example, the first blog post on this website was posted in 2012: ten years ago. But if you count the number of years listed in the archive there are 11 years. If you release an issue of a magazine once a year, then issue 11 (not issue 10) will be the issue released 10 years after you start not issue 10. If, like Chalkdust, you release issues two times a year, issue 21 (not issue 20) will be the 10 year issue.

Half-open intervals

An interval is called closed if it includes its starting and ending point, and open if it doesn't include them. A half-open interval includes one end point and not the other. Using half-open intervals makes counting things less difficult: including one endpoint but not the other is a bit like ignoring the final (or first) fence post so that there are the same number of post and panels.
In Python, the range function includes the first number but not the last (this is the sensible choice as including the final number and not the first would be very confusing). range(5, 8) includes the numbers 5, 6, and 7 (but not 8). By excluding the final number, the number of numbers in a range will be equal to the difference between the two input numbers.
Excluding the final item so that the number of items in a range is equal to the difference between the start and end is a great way to reduce opportunities for off-by-one errors, and isn't too hard to get used to.

Why start at 0?

We've seen a couple of causes of off-by-one errors, but we've not yet seen why this page's URL contains 99 rather than 100. This is because the numbering of blog posts started at zero. But why is it a sensible choice to start at 0?
Using a half-open range, the first \(n\) numbers starting at 1 would be range(1, n + 1); the first \(n\) numbers starting at 0 on the other hand would be range(0, n). The second option is neater, as you don't have to add one to the final number; the first option opens up more opportunities for off-by-one errors. This is one of the reasons why Python and many other programming languages start their numbering from 0.

Why doesn't everyone start at 0?

Starting at 0 and using half-open intervals to represent ranges of integers seem like good ways to help people avoid making off-by-one errors, but this choice is not perfect. If you want to write a range of numbers from 1 to 8 inclusive using this convention, you would have to write range(1, 9): forgetting to add one to the final number in this situation is another source of off-by-one errors.
It's also more natural to many people to start counting from 1, so some programming languages choose different conventions. The following table sums up the different possible conventions, which desirable properties they have, and which languages use them.
Convenction Languages using this convention Length of range is difference between endpoints range(START, n) contains \(n\) numbers range(START, n) contains START range(START, n) contains \(n\)
START=0, range includes first endpoint onlyPython, Javascript, PHP, Rust, C, C++
START=0, range includes last endpoint only
START=0, range includes both endpoints
START=0, range includes neither endpoint
START=1, range includes first endpoint only
START=1, range includes last endpoint only
START=1, range includes both endpointsMatlab, Julia, Fortran
START=1, range includes neither endpoint
(I don't know of any languages that use any of the other conventions, but if you have please let me know in the comments below and I'll add them.)
None of the conventions manages to remove all the possible sources of confusion, so it looks like off-by-one errors are here to stay.
      ×1                  
(Click on one of these icons to react to this blog post)

You might also enjoy...

Comments

Comments in green were written by me. Comments in blue were not written by me.
Hi!!!
Love your blog posts!
They make me get out of bed in the morning.
Just wanted to show my appreciation.
Cheers.
Anonymous#3728
×1                 Reply
 Add a Comment 


I will only use your email address to reply to your comment (if a reply is needed).

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li> <logo>
To prove you are not a spam bot, please type "i" then "n" then "t" then "e" then "g" then "e" then "r" in the box below (case sensitive):

Archive

Show me a random blog post
 2024 

Feb 2024

Zines, pt. 2

Jan 2024

Christmas (2023) is over
 2023 
▼ show ▼
 2022 
▼ show ▼
 2021 
▼ show ▼
 2020 
▼ show ▼
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

asteroids chebyshev palindromes databet crochet game of life triangles accuracy zines hats matrices simultaneous equations harriss spiral game show probability graphs turtles propositional calculus determinants misleading statistics runge's phenomenon stickers puzzles matrix of cofactors games draughts edinburgh curvature graph theory final fantasy manchester talking maths in public matrix multiplication python london underground golden spiral numerical analysis probability martin gardner stirling numbers craft sound guest posts captain scarlet mathsteroids dragon curves live stream noughts and crosses polynomials arithmetic standard deviation preconditioning royal institution world cup folding paper wave scattering pac-man oeis realhats the aperiodical frobel weak imposition ternary numbers dates pi approximation day london go quadrilaterals recursion php books menace sorting tennis radio 4 mathslogicbot hyperbolic surfaces phd mean royal baby logo coins cambridge youtube matrix of minors reddit speed finite element method data pascal's triangle european cup correlation big internet math-off logs hannah fry countdown sport mathsjam boundary element methods advent calendar datasaurus dozen bubble bobble geometry cross stitch geogebra video games anscombe's quartet fence posts christmas football fonts pythagoras manchester science festival 24 hour maths chess dinosaurs programming exponential growth inline code light map projections convergence chalkdust magazine data visualisation rhombicuboctahedron sobolev spaces people maths platonic solids gaussian elimination newcastle errors bempp finite group machine learning crossnumber reuleaux polygons weather station pizza cutting computational complexity signorini conditions flexagons folding tube maps interpolation braiding national lottery gather town estimation golden ratio pi christmas card electromagnetic field binary bodmas wool ucl raspberry pi javascript rugby hexapawn tmip plastic ratio news inverse matrices dataset error bars nine men's morris statistics approximation a gamut of games matt parker logic trigonometry gerry anderson latex fractals squares

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2012–2024