Friday, October 28, 2005

Algorithms for a Ten-Year Old

Yesterday my fifth-grade daughter, doing her math homework, asked
Is there a faster way to find greatest common factors other than with factor trees?
I live for these days. After I impressed her with Euclid's algorithm she asked
Is there a faster way to factor than with factor trees?
I thought for a while and then just answered "No."


  1. Lance, you take the time to explain Euclid's Algorithm, but lie about whether or not there are fast factorization algorithms? Shame. The answer should have been, "I don't know, but no one else does either".

    And wow, learning gcd, factorization, trees, etc in 5th grade? Its been a long time since I was in grade school, but I don't remember doing anything that advanced that early.

    Are you grooming a future complexity theorist?

  2. No, Lance responded like a true constructivist CS (or logic) person.

    For a constructivist "there is an object O" means "there is a procedure that produces O", and in this sense there is no better algorithm for a ten year old. I would certainly not be able to explain eliptic curves to a ten year old -- ten year olds are very strict constructionists.

    Janos Simon

  3. Quick theory question. Has factoring been proven to be NP complete? If so could you give a reference to the reduction?

  4. I don't understand why kids are taught to fing greatest common factors by factorization. I reinvented euclid's algorithm in junior high because it's easier. Then I taught it to a few other students, and the teacher started marking them wrong.

    Technically speaking, factorization *is* building a syntax tree, the question is whether it's possible to find factors more quickly than using erathosthenes's seive, to which the answer 'no' isn't exactly wrong - it's worthwile to do a seive for all possible factors up to around 2^32, which would make any speedups start providing benefits at values way beyond anything an elementary school student might work with.

  5. Factoring has not been
    proved NP-complete.
    If P is not NP, it is unlikely that factoring
    is NP complete.


    Since factor tree method
    is exponential, and a
    lot of algorithms of factoring are subexponential,
    so I think that answer
    to the last question should be Yes.

  6. I guess 5th grade IS a little early to learn quantum theory ;)

  7. Fifth Grade is too early for Quantum
    Computing (and Shor's algorithm) NOW.
    But in 1000 years- who knows.
    Over time Calculus has gone from
    being a Senior course in College to
    being a freshman course, and now in
    many High Schools. Some Computer Science
    concepts may do the same.
    Thought quantum- hard to say.

    Problem 4 on CS AP exam in the year 3000:
    Show that Factoring is in QP-P.

  8. This made me laugh out loud.

    I can remember the day my dad tried to explain parabolas as the path that falling objects take after I asked him for help on my math homework involving solving linear equations. I think my reaction was similar to your daughter's.

    Kris Hildrum

  9. Yes, calculus was pushed forward, but whole swaths of algebra and geometry, that used to make the eventual fruits of calculus more richly appreciated, were lost.
    Taking symbolic antiderivatives is a rather meaningless activity for me, and I'm less good at it, because I had less prior immersion in the domains where explicit ones turn out to exist (not that this is a huge loss).

    Lesson for us: kids need time to build some gut-level domain ontology before it's rewarding for them to study/design algorithms.

    Adults, too. The rage for order and intellectual mastery that drives much algorithmic research can get results, but in my experience it's more rewarding, and you get better algorithms, if you think 'with feeling' about specific problem examples, find relevances and anthropomorphize a bit, before trying to coerce a problem into an algorithmic paradigm.

  10. Yesterday my sixth-grade son, doing his math homework, asked Is there a faster way to divide a number by another other than with long division? I had no good answer to that. Any suggestions for an alternative to tedious long divisions?

    I expect that the reason why kids are taught to fing greatest common factors by factorization is that the main point is to understand the concept of factorization: associativity of multiplication, and the uniqueness of decomposition into prime factors. Greatest common factors, I expect, is just a side application to explore the concept.

  11. "Lesson for us: kids need time to build some gut-level domain ontology before it's rewarding for them to study/design algorithms."

    I can think of no better way to teach children algorithms than with computer graphics and then eventually video games. Perhaps that's just because that's how I first got into programming, but languages like Logo and Joe and Squeak seem to teach the concepts well.

  12. Claire: I would, along with your son, write a program which takes division problems as input and produces beautifully formatted Latex output. Then, have him use this program for all further problems and allow him to spend the remaining time reading Knuth, playing outside, etc.

  13. If factoring were NP-complete, then you would have NP = co-NP, which people think doesn't happen. Moreover, factoring is in BQP, and people think that NP-complete problems are well outside of BQP.

  14. Well it is something similar to comic I had read .. I guess it was xkcd or phdcomics...
    but the crux of it was that PhDs can't answer simple questions for sure because the depth in research makes them unsure.. ;)

  15. Solution to NP complete Hamilton Circuit Problem

    An algorithm solves at least a subset of the NP complete Hamilton Circuit problem in n^3 time.

  16. After my son (he is 5) saw the sorting mail packages episode on Curious George, he kept asking, so if we sort the packages it becomes easier? I think I must have answered yes to his 10 different articulations of the same question. Heaven!

    I am itching till he gets his addition skills up a bit so we can progress to sums of series.

    But in terms of spatial algorithms (something I have no expertise in), he seems to be doing something which other kids do as well, and which I don't see is well understood. How the kids solve those shape puzzles (some of those are hard!) is a bit beyond me.