views:

329

answers:

12

What non-programming-specific formulas do you use the most whilst working as a programmer?

I'm thinking of non-trivial formulas/theorems from the field of mathematics, logic or science that you constantly put in to practice. The type of formulas they would make you rote learn at uni and that appear in bold in textbooks, rather than lengthy algorithms.

Let us know why the formula comes in handy in your job.

I would say a theorem that even beginner programmers should be aware of is De Morgan's Law:

not (P and Q) = (not P) or (not Q)
not (P or Q) = (not P) and (not Q)
+2  A: 

I think about big-O notation whenever I write something new that I know will be called repeatedly in my programs. That's not exactly a formula, more of an understanding of how your algorithm will scale asymptotically.

Most of the mathematical/scientific problems in programming that I've seen are specific enough that you can pick up formulae when you're learning the spec for a new project. If you're writing a project spec, there's a lot of domain-specific places in which understanding the math can tell you what's even possible.

James Thompson
+2  A: 

For some reason I keep referring to this page over and over again (cross product).

shoosh
+6  A: 
if (x & 1) // evaluates to true if x is odd

This is equal to:

if (!(x % 2))

but is faster.

Tyler
Most compilers will optimize a modulus by a constant power of 2 into a bitwise AND anyways. If x is unsigned, they are equally fast, but if x is signed, the compiler has to generate a slightly different code sequence that is correct for positive and negative numbers.
Adam Rosenfield
this is faster for the compilers ... but humans who have to maintain the code ? :)
Learning
Tyler
I am so used to this I read the first version better. @Adam, Sign only becomes an issue where signed integers are not represented in two's complement on the target system.
strager
+3  A: 

Depends on which field you're applying knowledge. Personally, I use a lot of linear equations of the form

y = mx + b

which is basic highschool stuff, but you'd be amazed how useful it is when you want to map one range of values to another in a linear fashion. What amazes me is that most of the math I use is actually trivial, even though I have an engineering degree under my belt. I suppose it's more a matter of looking at a problem and knowing which math to use as part of a solution.

Charlie Salts
+4  A: 

For vectors P and Q,

  1. P.Q = |P||Q|cos(t)
  2. P projected onto Q = (( P.Q ) / ( Q.Q ))*Q
  3. P's perpendicular to Q = P - (( P.Q ) / ( Q.Q ))*Q

Linear algebra is the bread and butter of 3D games programming. It becomes a reflex.

There's a lot of this too.

Crashworks
I'd -1 for the usage of "games programming" and "3D graphics programming" as synonymous, but my 1300 is too pretty.
chaos
+3  A: 
Kevin Loney
Woah! How did you get the math markup?
Crashworks
courtesy of mathworld: http://mathworld.wolfram.com/Determinant.html
Kevin Loney
+2  A: 

I use boolean algebra a lot, particularly de Morgen's laws:

(ab)' = a' + b'

and

(a + b)' = a'b'

where:

ab = a AND b
a' = NOT a
a + b = a OR b

(it's engineering notation but I like it)

also the truth statement:

a + ab = a

You'll be surprised how often people code redundant logic statements like that.

You can use this to refactor things like:

a + a'b

to:

  (a'(a'b'))'
= (a'b')'
= a + b

Some might say that's obvious but there's a difference between being (supposedly) obvious (lots of wrong things have seemed obvious) or doing truth tables and quickly proving it.

cletus
+4  A: 
log_b(n) = log(n) / log(b)

I use that all the time for so many things, particularly when working out how long an operation will take and not having a calculator that calculates log_2.

Another rule I use so regularly that I don't even think about it any more is

!(a && b) == !a || !b
!(a || b) == !a && !b

And all the alternatives of it. In very tight loops across (say) image pixels, being able to reduce from two inversions and a logical operator to one logical operation and one inversion can save a lot of time and usually make the code more readable.

Adam Hawes
That second rule is De Morgans Law (which the poster set out as an example). Maybe you didn't realize it.
Tyler
I did know it, but forgot the name. It's been a long time since I had to reference it by name :)
Adam Hawes
+2  A: 

The Pareto principle otherwise known as the "80-20 Rule". I find this principal crops up again and again. I use it for project estimation because I just know that the last 20% of the project is really going to take 80% of the effort

Harry
Looking at the other answers - i'm guessing that i'm way off the mark LOL
Harry
+1 I'm also a Pareto groupie
Robert Gould
+1  A: 

I use basic trig pretty regularly, x = r * cos(theta), y = r * sin(theta).

Jeb
A: 

Well, it's not exactly a 'formula' per say but I use:

White space is FREE!

In other words, throw in a return or two here and there so your code is easier to read.

I never did well with math in college and still have no idea how I managed to pass that big O notation class...

GeoffreyF67
dude...
Beska
LOL - it's true tho!
GeoffreyF67
+1  A: 
quant_dev
What the heck field are you in? This looks very cool. (Math that I don't grok is always cool.)
Beska
Mathematical finance.
quant_dev
Ahh...my prof, Skiena, thought I should go into that. Maybe I should have!
Beska