Simple to program yet computationally difficult functions

Question

I need an example of a slow Excel sheet that could exist in the real world. Problem is I'm not sure what sort of functions are computationally difficult.

Are there any sort of (maths?) functions that are easy enough to program that they can be used in Excel, yet computationally expensive?

Something which has a real world application is a bonus.

Answer 1

Fun: Given a set of gear wheels, compute the subset which interconnected comes closest to a target ratio.

Simple: Compute the factorial of a given integer.

Answer 2

I wonder if someone out there has written the Mandelbrot code for Excel. That is simple yet expensive. Unfortunately, I don't know how Excel would handle the looping, unless you start writing VBA, and I assume you mean Excel only without scripting.

No bonus, because no real world application I can think of.

Answer 3

Some examples:

• Interest rates on bank accounts. A bank account is growing over time. You know its value at several points. Determine the interest rate of the bank account. (There is no closed-form algebraic solution to this expression, although it usually converges quickly.)

• Annual company meetings. You have a list of n people from a company directory. You're making the notes for the annual company meeting. Construct every possible committee that can be formed from these n people. and enumerate each pair of committees. Now assign each pair of committees to one of two conference rooms. Find the smallest n that will guarantee that there are four committees, such that:

  • All pairings of these committees fall into the same group. (You only want to reserve one conference room.)
  • All people belong to an even number of committees. (You want to use both sides of the committee signs and save paper.)

• Packing boxes. You are the logistics manager of a warehouse and would like to pack a set of products into the smallest crate possible. The volume of each crate exceeds the volume of the set of products. Determine which crate size will allow all the items to fit but will minimize the amount of wasted space.

P.S. It turns out that the committee example is equivalent to trying to calculate Graham's number, which is an astronomically, incomprehensibly huge value.

Answer 4

You could try and compute the prime factors of large integers (http://en.wikipedia.org/wiki/Integer_factorization) this becomes computationally infeasible for large integers

Real world application: breaking RSA

Answer 5

The Ackermann function on a bunch of numbers? Can also make a pretty graph.

check it out