Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Space Complexity of Number-theoretic Algorithms

  1. Feb 15, 2006 #1
    Can you write an example where a space complexity of any number-theoretic algorithm is calculated? Thanks In Advance.
  2. jcsd
  3. Feb 15, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    Have you tried google? Try 'euclidean algorithm' and 'complexity', you'll get piles of examples where the time and space complexity is discussed. I'd expect most textbooks covering complexity would have an example from number theory as well (the euclidean algorithm is probably common here as well being a very 'classic' algorithm)
  4. Feb 16, 2006 #3
    Yes, I have. I have found examples where the time complexity of number-theoretic algorithms is discussed only.
  5. Feb 16, 2006 #4


    User Avatar
    Science Advisor
    Homework Helper


    http://pharos.cpsc.ucalgary.ca/Dienst/UI/2.0/Describe/ncstrl.ucalgary_cs/1989-376-38 [Broken]

    (first hit from "space complexity" euclidean algorithm)

    You might want to check Andrew Odlyzko's webpage


    It's filled with number theory algorithms, the handfull I've read included time and space complexity discussions.
    Last edited by a moderator: May 2, 2017
  6. Feb 17, 2006 #5
    Thank you. This is very interesting links.
  7. Feb 18, 2006 #6
    Dear shmoe.

    I have read the part of these links. Not long ago I read "A Course in Number Theory and Cryptography" by Neal Koblitz. I have used Neal Koblitz's model of bit operations for estimation of the time complexity of my algorithm.

    If you read Neal Koblitz's book say please what do you think about next questions?
    Is this model a RAM with infinity space and word length?
    Can I speak that the space complexity of my algorithms is the number of bits using to story information?
    Thanks In Advance.
  8. Feb 20, 2006 #7
    I havent read the book, but normally when we speak of time and space complexity, we do in terms of Turing Machine (commonly referred to as Turing Machine model). I presume you are aware of this and hence wont delve further into this.

    Now when one speaks of RAM model, one has to be very precise as to which one he/she is referring to.

    There are two types of RAM models,
    1. General Unit Cost RAM model
    Unit cost inucurred per instruction execution
    2. Log-cost RAM model
    Cost incurred per instruction execution is proportional to logarithm on the size of the operands

    The general unit cost RAM model is much more powerful than our Turing Machine. The Turing Machine equivalent in RAM models is the log-cost RAM model. Hence, if you are using the RAM model, one normally should adhere to log-cost RAM model. However, working with unit-cost RAM model is simpler and hence we do a work around.

    Work Around :
    We make sure that all the input operands are polynomially bounded in the input size. For such a unit cost RAM model, there is an equivalent log-cost RAM model and thereby a Turing model.

    Most algorithms (especially the number theoretic algorithms that you are interested in) today commonly appeal to unit-cost RAM model in the way i described above.

    -- AI
  9. Feb 20, 2006 #8
    Thank you.
    If I understand rightly then you mean "the uniform cost criterion" and "the logarithmic cost criterion" from

    http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fivese1.html" [Broken]

    I deal with big numbers. So I think to use the logarithmic cost criterion, i.e. O(log N) units of space for a number N (or O(log N) bits for a number N). Am I right?
    Last edited by a moderator: May 2, 2017
  10. Feb 21, 2006 #9

    Sort of close but not completely. Our computers are known to simulate Turing Machines. As i said earlier, the unit cost RAM model is far more powerful than our Turing Machine. That is, a unit cost RAM model can outperform our computers at certain things and obviously, since we are looking at things that our computers are capable of doing, we wouldnt want to work with unit cost RAM model.

    -- AI
    Last edited by a moderator: May 2, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook