Miller-Rabin Primality Test

Math ∩ Programming

Problem: Determine if a number is prime, with an acceptably small error rate.

Solution: (in Python)

Discussion: This algorithm is known as the Miller-Rabin primality test, and it was a very important breakthrough in the study of probabilistic algorithms.

Efficiently testing whether a number is prime is a crucial problem in cryptography, because the security of many cryptosystems depends on the use of large randomly chosen primes. Indeed, we’ve seen one on this blog already which is in widespread use: RSA. Randomized algorithms also have quite useful applications in general, because it’s often that a solution which is correct with probability, say, $latex 2^{-100}$ is good enough for practice.

But from a theoretical and historical perspective, primality testing lied at the center of a huge problem in complexity theory. In particular, it is unknown whether algorithms which have access to randomness and can output probably correct answers are more…

View original post 425 more words

pypy compilation error

Am trying to compile pypy on my core i7 3632 QM machine with 4GB of memory. But i run into pdb with an error “can’t allocate memory” Am running a ubuntu 13.04 with the latest updates. Here’s the error stack below..

 

[platform:execute] gcc /tmp/usession-default-1/platcheck_56.o -pthread -lrt -lrt -o /tmp/usession-default-1/platcheck_56
[platform:execute] gcc -c -O3 -pthread -fomit-frame-pointer -Wall -Wno-unused /tmp/usession-default-1/platcheck_57.c -o /tmp/usession-default-1/platcheck_57.o
[platform:execute] gcc /tmp/usession-default-1/platcheck_57.o -pthread -lrt -lrt -o /tmp/usession-default-1/platcheck_57
[751b] translation-task}

[Timer] Timings:
[Timer] annotate                       — 287.2 s
[Timer] ==========================================
[Timer] Total:                         — 287.2 s
[translation:ERROR] Error:
[translation:ERROR]  Traceback (most recent call last):
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/translator/goal/translate.py”, line 317, in main
[translation:ERROR]     drv.proceed(goals)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/translator/driver.py”, line 733, in proceed
[translation:ERROR]     return self._execute(goals, task_skip = self._maybe_skip())
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/translator/tool/taskengine.py”, line 114, in _execute
[translation:ERROR]     res = self._do(goal, taskcallable, *args, **kwds)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/translator/driver.py”, line 284, in _do
[translation:ERROR]     res = func()
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/translator/driver.py”, line 321, in task_annotate
[translation:ERROR]     s = annotator.build_types(self.entry_point, self.inputtypes)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 93, in build_types
[translation:ERROR]     return self.build_graph_types(flowgraph, inputcells, complete_now=complete_now)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 149, in build_graph_types
[translation:ERROR]     self.complete()
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 203, in complete
[translation:ERROR]     self.complete_pending_blocks()
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 198, in complete_pending_blocks
[translation:ERROR]     self.processblock(graph, block)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 348, in processblock
[translation:ERROR]     self.flowin(graph, block)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 412, in flowin
[translation:ERROR]     self.consider_op(block, i)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 606, in consider_op
[translation:ERROR]     resultcell = consider_meth(*argcells)
[translation:ERROR]    File “<4318-codegen /home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py:646>”, line 3, in consider_op_getattr
[translation:ERROR]     return arg.getattr(*args)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/unaryop.py”, line 724, in getattr
[translation:ERROR]     return bookkeeper.pbc_getattr(pbc, s_attr)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/bookkeeper.py”, line 605, in pbc_getattr
[translation:ERROR]     return first.s_read_attribute(attr)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/description.py”, line 974, in s_read_attribute
[translation:ERROR]     return self.bookkeeper.immutablevalue(value)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/bookkeeper.py”, line 396, in immutablevalue
[translation:ERROR]     result.dictdef.generalize_value(self.immutablevalue(ev))
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/annotator/bookkeeper.py”, line 477, in immutablevalue
[translation:ERROR]     x._cleanup_()
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/interpreter/mixedmodule.py”, line 123, in _cleanup_
[translation:ERROR]     self.getdict(self.space)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/interpreter/mixedmodule.py”, line 116, in getdict
[translation:ERROR]     w_value = self.get(name)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/interpreter/mixedmodule.py”, line 69, in get
[translation:ERROR]     w_value = self.getdictvalue(space, name)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/interpreter/mixedmodule.py”, line 81, in getdictvalue
[translation:ERROR]     return self._load_lazily(space, name)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/interpreter/mixedmodule.py”, line 91, in _load_lazily
[translation:ERROR]     w_value = loader(space)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/interpreter/mixedmodule.py”, line 190, in ifileloader
[translation:ERROR]     value = eval(spec, d)
[translation:ERROR]    File “<string>”, line 1, in <module>
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/pypy/module/pyexpat/interp_pyexpat.py”, line 405, in get_expat_version
[translation:ERROR]     return space.wrap(rffi.charp2str(XML_ExpatVersion()))
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/rtyper/lltypesystem/rffi.py”, line 243, in wrapper
[translation:ERROR]     res = call_external_function(*real_args)
[translation:ERROR]    File “<518-codegen /home/anand/playspace/languages/python/pypy/rpython/rtyper/lltypesystem/rffi.py:169>”, line 6, in call_external_function
[translation:ERROR]     res = funcptr()
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/rtyper/lltypesystem/lltype.py”, line 1291, in __call__
[translation:ERROR]     return callb(*args)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/rtyper/lltypesystem/ll2ctypes.py”, line 1208, in __call__
[translation:ERROR]     cfunc = get_ctypes_callable(self.funcptr, self.calling_conv)
[translation:ERROR]    File “/home/anand/playspace/languages/python/pypy/rpython/rtyper/lltypesystem/ll2ctypes.py”, line 1140, in get_ctypes_callable
[translation:ERROR]     libpath = ctypes.util.find_library(libname)
[translation:ERROR]    File “/usr/lib/python2.7/ctypes/util.py”, line 253, in find_library
[translation:ERROR]     return _findSoname_ldconfig(name) or _get_soname(_findLib_gcc(name))
[translation:ERROR]    File “/usr/lib/python2.7/ctypes/util.py”, line 242, in _findSoname_ldconfig
[translation:ERROR]     f = os.popen(‘/sbin/ldconfig -p 2>/dev/null’)
[translation:ERROR]  OSError: [Errno 12] Cannot allocate memory
[translation:ERROR] Processing block:
[translation:ERROR]  block@3 is a <class ‘rpython.flowspace.flowcontext.SpamBlock’>
[translation:ERROR]  in (pypy.module.imp.interp_imp:155)is_builtin
[translation:ERROR]  containing the following operations:
[translation:ERROR]        v45 = getattr(space_2, (‘str0_w’))
[translation:ERROR]        v46 = simple_call(v45, w_name_0)
[translation:ERROR]        v44 = getattr(space_2, (‘builtin_modules’))
[translation:ERROR]        v47 = contains(v44, v46)
[translation:ERROR]        v48 = is_true(v47)
[translation:ERROR]  –end–
[translation] start debugger…
> /usr/lib/python2.7/ctypes/util.py(242)_findSoname_ldconfig()
-> f = os.popen(‘/sbin/ldconfig -p 2>/dev/null’)

 

Looks like it is time to dig around and understand the pypy architecture.. Phew i was hoping to avoid that at the first run.. oh well as always it nothing is ever as simple as it seems.. :P

UPDATE 3 July 2013 00:53 AM
Hypothesis 1: i have been running my OS from a pendrive with misconfigured swap partition. Time to edit and fix /etc/fstab and reboot to test.

UPDATE 12 July 2013 19:37 PM
OK that lack of swap partition was the problem. I was able to compile pypy successfully. See details below:
I am using a Dell inspiron with core i7 3rd Gen. processor and 4 GB RAM.

time python rpython/bin/rpython pypy/goal/targetpypystandalone.py
[Timer] Timings:
[Timer] annotate — 421.1 s
[Timer] rtype_lltype — 1713.8 s
[Timer] backendopt_lltype — 193.7 s
[Timer] stackcheckinsertion_lltype — 150.8 s
[Timer] database_c — 213.1 s
[Timer] source_c — 404.4 s
[Timer] compile_c — 397.8 s
[Timer] ===========================================
[Timer] Total: — 3494.7 s

real 59m48.626s
user 51m37.880s
sys 0m4.224s

Time try out the other target numpy. And then may be i can try my hand at creating a new target, perhaps scikit-learn?? We’ll see if i am up to that task

UPDATE: 12 July 19:42 PM
Hmm numpy fails with the python rpython. some signature mismatch.. Here’s the error stack

[Timer] Timings:
[Timer] annotate — 2.0 s
[Timer] ========================================
[Timer] Total: — 2.0 s
[translation:ERROR] Error:
[translation:ERROR] Traceback (most recent call last):
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/translator/goal/translate.py”, line 321, in main
[translation:ERROR] drv.proceed(goals)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/translator/driver.py”, line 732, in proceed
[translation:ERROR] return self._execute(goals, task_skip = self._maybe_skip())
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/translator/tool/taskengine.py”, line 114, in _execute
[translation:ERROR] res = self._do(goal, taskcallable, *args, **kwds)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/translator/driver.py”, line 283, in _do
[translation:ERROR] res = func()
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/translator/driver.py”, line 320, in task_annotate
[translation:ERROR] s = annotator.build_types(self.entry_point, self.inputtypes)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 93, in build_types
[translation:ERROR] return self.build_graph_types(flowgraph, inputcells, complete_now=complete_now)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 149, in build_graph_types
[translation:ERROR] self.complete()
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 203, in complete
[translation:ERROR] self.complete_pending_blocks()
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 198, in complete_pending_blocks
[translation:ERROR] self.processblock(graph, block)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 348, in processblock
[translation:ERROR] self.flowin(graph, block)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 412, in flowin
[translation:ERROR] self.consider_op(block, i)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/annrpython.py”, line 606, in consider_op
[translation:ERROR] resultcell = consider_meth(*argcells)
[translation:ERROR] File “”, line 3, in consider_op_simple_call
[translation:ERROR] return arg.simple_call(*args)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/unaryop.py”, line 155, in simple_call
[translation:ERROR] return obj.call(getbookkeeper().build_args(“simple_call”, args_s))
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/unaryop.py”, line 737, in call
[translation:ERROR] return bookkeeper.pbc_call(pbc, args)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/bookkeeper.py”, line 669, in pbc_call
[translation:ERROR] results.append(desc.pycall(schedule, args, s_previous_result, op))
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/description.py”, line 297, in pycall
[translation:ERROR] inputcells = self.parse_arguments(args)
[translation:ERROR] File “/home/anand/playspace/languages/python/pypy/rpython/annotator/description.py”, line 265, in parse_arguments
[translation:ERROR] (self.name, e.getmsg()))
[translation:ERROR] TypeError: (‘signature mismatch: numpy_compile() takes exactly 1 argument (2 given)’, <
[translation:ERROR] Occurred processing the following simple_call:
[translation:ERROR] (KeyError getting at the binding!)
[translation:ERROR] v2 = simple_call((function numpy_compile), v0, v1)
[translation:ERROR] In :
[translation:ERROR] Happened at file pypy/goal/targetnumpystandalone.py line 36
[translation:ERROR]
[translation:ERROR] ==> a = numpy_compile(bc, size)
[translation:ERROR] a = a.compute()
[translation:ERROR]
[translation:ERROR] Known variable annotations:
[translation:ERROR] v0 = SomeString(no_nul=True)
[translation:ERROR] v1 = SomeInteger(knowntype=int, nonneg=False, unsigned=False)>)
[translation:ERROR] Processing block:
[translation:ERROR] block@39 is a
[translation:ERROR] in (targetnumpystandalone:33)main
[translation:ERROR] containing the following operations:
[translation:ERROR] v2 = simple_call((function numpy_compile), v0, v1)
[translation:ERROR] v3 = getattr(v2, (‘compute’))
[translation:ERROR] v4 = simple_call(v3)
[translation:ERROR] –end–
[translation] start debugger…

pg’s post on startup investing

Just a bunch of thoughts(occurred while reading actively) about the blog post here.

<blockquote>

Does that mean investors will make less money? Not necessarily, because there will be more good startups. The total amount of desirable startup stock available to investors will probably increase, because the number of desirable startups will probably grow faster than the percentage they sell to investors shrinks.

 

There’s a rule of thumb in the VC business that there are about 15 companies a year that will be really successful. Although a lot of investors unconsciously treat this number as if it were some sort of cosmological constant, I’m certain it isn’t. There are probably limits on the rate at which technology can develop, but that’s not the limiting factor now. If it were, each successful startup would be founded the month it became possible, and that is not the case. Right now the limiting factor on the number of big hits is the number of sufficiently good founders starting companies, and that number can and will increase. There are still a lot of people who’d make great founders who never end up starting a company. You can see that from how randomly some of the most successful startups got started. So many of the biggest startups almost didn’t happen that there must be a lot of equally good startups that actually didn’t happen.

There might be 10x or even 50x more good founders out there. As more of them go ahead and start startups, those 15 big hits a year could easily become 50 or even 100.

</blockquote>

       paul graham is an optimist and believes total economic activity(productive output??) will only grow in the future.. hmm..
        Am reading his post on trends in startups. and i still think his optimism is closer to the truth.
        the reasoning he gives for his conclusion  is via negativa, but most likely i like optimism is why i agree, any case.
        I also realize the reason i like his posts so much, he knows the basic math of stats and calculus,
            and better can express his opinions and ideas about trends in reasonably simple words, though,
            i think his avoidance of equations makes his posts a little verbose, but it is perhaps justified(nay pragmatic), given the math hate/fear that prevails and topics he writes on.

Right now, VCs often knowingly invest too much money at the series A stage. They do it because they feel they need to get a big chunk of each series A company to compensate for the opportunity cost of the board seat it consumes. Which means when there is a lot of competition for a deal, the number that moves is the valuation (and thus amount invested) rather than the percentage of the company being sold. Which means, especially in the case of more promising startups, that series A investors often make companies take more money than they want.           Like a lot of bad things, this didn’t happen intentionally.

 

He’s definitely an optimist :-P,
            I would have interpreted,Series A investors wanting to invest a minimal amount of the company stock’s worth as definitely malicious planning, but then i have no real experience.

            <blockquote> You can’t fight market forces forever.</blockquote>, That’s a great quote for any article on economy.