Like Tree1Likes

Quick question on mathematical notation (translating to C)

This is a discussion on Quick question on mathematical notation (translating to C) within the General Discussions forums, part of the Community Boards category; Originally Posted by gardhr I'm basing it on the heuristic that most papers written about number theory seem to use ...

  1. #16
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,973
    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".
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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"

Page 2 of 2 FirstFirst 12
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, 06:44 AM
  2. big O notation question
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 11-08-2008, 02: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, 08:31 AM
  5. Mathematical Question
    By rmullen3 in forum C++ Programming
    Replies: 4
    Last Post: 12-29-2001, 08:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21