Thread: Quick question on mathematical notation (translating to C)

  1. #16
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by gardhr
    I'm basing it on the heuristic that most papers written about number theory seem to use that convention.

    Specifically, it's a lower bound given for the Miller-Rabin primality test, described here.
    The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #17
    Registered User gardhr's Avatar
    Join Date
    Apr 2011
    Posts
    151
    Quote Originally Posted by laserlight View Post
    The expression is in the context of computational complexity, and indeed it is used in "big-O" notation throughout the paper. Basically, the base does not matter since they are considering things "asymptotically".
    The equation in question relates to the actual lower bound of trial number bases, not the complexity of the algorithm. Or am I reading it wrongly?

    "For an integer n , let G(n) denote the smallest x such that the
    primes < x generate the multiplicative group modulo n . We offer heuristic
    arguments and numerical data supporting the idea that
    G(n) < (log 2)^-1 log n log log n"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Expression: Convert infix notation to postfix notation.
    By Nutshell in forum C Programming
    Replies: 7
    Last Post: 02-27-2010, 07:44 AM
  2. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 03:53 PM
  3. [OT] help translating and phrazing
    By jabka in forum C++ Programming
    Replies: 1
    Last Post: 05-04-2007, 11:37 AM
  4. Code translating
    By Liger86 in forum C Programming
    Replies: 3
    Last Post: 12-27-2002, 09:31 AM
  5. Mathematical Question
    By rmullen3 in forum C++ Programming
    Replies: 4
    Last Post: 12-29-2001, 09:44 PM