The world's largest prime

Courtesy Fabrice Bellard, here is a compact computer program in C to print out the world's largest known prime.

int m=167772161,N=1,t[1<<25]={2},a,*p,i,e=34893349,s,c,U=1;g(d,h){for(i=s;i<1<<24;i*=2)d=d*1LL*d%m;for(p=t;p<t+N;p+=s)for(i=s,c=1;i;i--)a=p[s
]*(h?c:1LL)%m,p[s]=(m+*p-a)*(h?1LL:c)%m,a+=*p,*p++=a%m,c=c*1LL*d%m;}main(){while(e
/=2){N*=2;U=U*1LL*(m+1)/2%m;for(s=N;s/=2;)g(17,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;for(s=1;s<N;s*=2)g(29606852,1);for(a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;}while(!*--p);for(t[0]--;p>=t;)putchar(48+*p--);}

The program is just 438 characters in length. It compiles quite quickly on the MacBook Pro and requires less than 5 minutes of running time.

This number, the largest known prime, belongs to a class of primes called Mersenne primes and has the value  2^43112609-1. It has no less than 13 million digits. I ran the program earlier today, and have pasted the first ten lines or so of the output below. I have a little mnemonic scheme to remember long strings of numbers and so I created a mnemonic to remember the first ten digits of the number. And so if you ever wanted to commit to memory the digits of the world's largest prime, you can start right here :

Harvard-Kyoto : a very brief note

A follow up to my post on the Tamil writing system. Some people had asked what the Harvard-Kyoto system referenced in the original post was and so, a few words on Harvard-Kyoto.

Harvard-Kyoto is a transliteration scheme for Devanagari. I am making a conscious attempt to keep the learning curve for this system as short as possible, and so, in that spirit, a very brief summary of Harvard-Kyoto is given below.

   a A i I u U R RR lR lRR e ai o au M H
   k kh g gh G c ch j jh J
   T Th D Dh N t th d dh n
   p ph b bh m y r l v z S s h

Anybody who has learnt Hindi would know what I am referring to here. These are the basic Devanagari vowels and consonants written out in ASCII. You can also refer to the Wikipedia entry on Harvard-Kyoto which is available here. That is more or less all the introduction you need to understand Harvard-Kyoto.

Comment : Email to Schelling on employees having to be "on" all the time

Below is an excerpt from my email to Nobelist Thomas Schelling on an issue that is increasingly affecting a lot of employees around the world, not the least back office workers in India.

==

It seems that the concept of credible commitment has applicability to the "being on" problem within organizations. Organization behaviorists have been concerned for a while now about the increasing demands on employees to be *on* - on email, on Blackberries, on call - and not just on during work hours, but on all the time.

"Being on" for an employee implies greater costs (exertion, et cetera) borne by employees. It is unclear that there is always a significant benefit arising out "being on" outside of work hours. The benefit to the employee or the company may be marginal. In many cases, it may, in fact, be more efficient for an employee to deal with all of her email in one shot than to break up her work-day by frequently checking email because these interruptions may require the employee to stop work on whatever it is she (or he) may be working on. The breaking up of the work-day may take a physical as well as psychological toll on employees - people want to help others, but first, they want to just get their own jobs done. Furthermore, in many cases, there is nothing happening outside of work hours that requires the employees to "be on" in the first place.

This may be modelled using the Prisoner's Dilemma matrix. Assume that we have two players. If both players checked email only during work hours, then both of them would benefit. If one of them defected and decided to check email all the time, he would be perceived as a good employee, and the other employee would get the Sucker's Payoff, which would be lower than if they both cooperated. That means that the only Nash Equilibrium is where both players defect.

It is, however, in the interest of the organization as a whole for employees to be satisfied, and so it might make sense for companies or units within companies to set limits on when employees are required to be on. Today, more and more employees are complaning that they are being overloaded with work. They feel tired. They feel overwhelmed. But more work hours does not equal more work done. If organizations made a credible commitment to employees, say, by installing software on the devices of the employees, so that they would not have to "be on" unless required, then employees may not feel it nescessary to analyze for equilibria.  It seems that by encouraging employees to Cooperate at the organizational or sub-organizational level, one may realize more productive - and happier - employees.

==

A breakthrough result in cryptography

Stanford's Craig Gentry's paper on the first ever fully homomorphic encryption scheme has been picked up recently by a mainstream publication. At least, insofar as the American Scientist qualifies. An article by Brian Hayes (thanks, Three Quarks Daily!):

Alice hands bob a locked suitcase and asks him to count the money inside. “Sure,” Bob says. “Give me the key.” Alice shakes her head; she has known Bob for many years, but she’s just not a trusting person. Bob lifts the suitcase to judge its weight, rocks it back and forth and listens as the contents shift inside; but all this reveals very little. “It can’t be done,” he says. “I can’t count what I can’t see.”
Alice and Bob, fondly known as the first couple of cryptography, are really more interested in computational suitcases than physical ones. Suppose Alice gives Bob a securely encrypted computer file and asks him to sum a list of numbers she has put inside. Without the decryption key, this task also seems impossible. The encrypted file is just as opaque and impenetrable as the locked suitcase. “Can’t be done,” Bob concludes again.
But Bob is wrong. Because Alice has chosen a very special encryption scheme, Bob can carry out her request. He can compute with data he can’t inspect. The numbers in the file remain encrypted at all times, so Bob cannot learn anything about them. Nevertheless, he can run computer programs on the encrypted data, performing operations such as summation. The output of the programs is also encrypted; Bob can’t read it. But when he gives the results back to Alice, she can extract the answer with her decryption key.
The technique that makes this magic trick possible is called fully homomorphic encryption, or FHE. It’s not exactly a new idea, but for many years it was viewed as a fantasy that would never come true. That changed in 2009, with a breakthrough discovery by Craig Gentry, who was then a graduate student at Stanford University.  

Here is a link to the incredible result first published in STOC. This is, of course, an absolutely breakthrough result and it has led to a number of subsequent papers which have extended the concept in many ways. There has been a number of subsequent papers on this topic by another rising star, Vinod Vaikuntanathan, who has this to say on a first application of the system.

When I asked Vaikuntanathan what application he thought might be deployed first, he had another suggestion: spam filtering. If you publish a public key and invite correspondents to send you encrypted email, a spammer can take advantage of the key to encrypt advertisements and the other effluvia that fills our mailboxes. Spam-filtering services cannot read and reject the encrypted spam unless you are willing to share your decryption key; homomorphic encryption could solve that problem.

Jury awards Apple $1bn in damages from Samsung

The verdict on Apple Inc. v. Samsung Electronics:

A jury has ruled that Samsung should pay Apple $1.05bn (£665m) in damages in an intellectual property lawsuit in the US.

It said that several of Samsung's devices had infringed Apple's software and design patents.

The jury rejected Samsung's claims that several of its patents had been breached and awarded it no damages.

Apple may now seek an import ban of some of its rival's products, blocking them from the US market.

Chris Anderson on innovation

Chris Anderson on how web video is powering innovation worldwide :

Coursera Hits 1 Million Students, With Udacity Close Behind

An article in the Chronicle of Higher Education about Coursera, a company co-founded by Stanford's Andrew Ng :

Coursera, an upstart company working with selective universities to offer free online courses, announced this week that it had reached one million registered students. A rival company, Udacity, which also offers what have become known as Massive Open Online Courses, or MOOC’s, says it has more than 739,000 students.

The numbers, however, are more symbolic of interest in free online courses than indicative of the amount of learning taking place. For instance, a co-founder of Coursera, Andrew Ng, noted in an e-mail interview that the number of active students is significantly lower because many registrations are for courses that have not yet begun. And many people sign up for the free courses but don’t end up following through by doing the coursework.

Students in MOOC’s typically watch short video lectures, complete automatically graded tests or assignments, and use online communities to work through concepts they don’t understand. In most cases, no official university credit is given, but providers of the programs plan to make money by offering students who finish the courses a certificate if they pay a small fee.

Coursera has signed up some of the world’s best-known universities, including Princeton University and the University of Virginia. Udacity, which works with individual professors rather than with institutions, has attracted a range of well-known scholars. Both companies started with a focus on courses in computer science, but Coursera is now expanding into a variety of disciplines.

NTU Scientist Invents Pocket Living Room TV

A new pocket living room TV from Nanyang Technological University:

Leaving your TV show midway because you had to leave your home will no longer happen as you can now ‘pull’ the programme on your TV screen onto your tablet and continue watching it seamlessly.

You can also watch the same TV show or movie together with your family and friends, no matter which part of the world they are in. Not only that but you’ll be able to discuss the show, whether you are on your personal tablet or smart phone, through a channel of your choice, be it video chat, voice or text.

The world’s first 'pick up and throw back' video feature allows your video and chat sessions to be screened wherever you go, providing continuous social engagement in today’s world.

This innovative multi-screen mobile social TV experience is now being made into reality by Assistant Professor Wen Yonggang from the School of Computer Engineering, Nanyang Technological University (NTU). It has already attracted the attention of both local and international telecommunication giants who have expressed interest in integrating this technology into their existing cable networks as a market differentiator for cable television and mobile networks. With discussions currently underway, the public here can expect to see videos and TV shows on the go together with their friends on the ‘cloud’ in about two years’ time.

The theme for August and office hours

Just a note to say that the theme for August is "Innovation and Competitive Strategy", and that the next office hours are on September 3, October 1 and November 5 between 7:30 and 8:15 am PST.

Curiosity, Mars Rover, will phone home

From GCN.com :

Now that the Mars Science Laboratory rover, better known as Curiosity, has landed safely in a Martian crater, it can begin its exploration of the surface in search of evidence of life on the Red Planet.

One key to what scientists find out about Mars will be NASA’s Deep Space Network, a kind of interplanetary Internet that will carry the data Curiosity collects the 139 million miles or so (that’s the average distance, but it can vary greatly depending on the planets’ orbits) back to Earth.

The Deep Space Network (DSN), which also carries communications from other space craft within and without the solar system, comprises large dish antenna arrays at three locations approximately 120 degrees apart on Earth: at Goldstone, Calif., in the Mojave Desert; near Madrid, Spain; and near Canberra, Australia.

Apple Patent Shows Wearable Computing Plans

From Phys.Org :

Like Google, Apple has plans to win recognition as wearable computing leaders. Patently Apple reports on a patent that was filed by Apple in January last year but made known earlier this week. The patent application is causing a stir over what Apple has in mind to compete with Google over the latter’s highly anticipated Project Glass heads-up display. The Apple patent in question, titled “Display resolution increase with mechanical actuation,” speaks of multiple “embodiments,” but the concept appears to relate to raising the quality of a display placed over a wearer’s eye.

Human Energy to Power Portable Electronics

Research at the University of Auckland on converting human energy into battery power :

Technology created by researchers from The Auckland Bioengineering Institute (ABI), which makes it possible to convert human movement into battery power, could in the future enable people to charge their electronic devices while they walk.

This is because artificial muscle generator technology developed by the ABI’s Biomimetics Lab can scavenge latent energy from human motion to directly power devices and put power where it's needed.

Dr Tom McKay, Dr Ben O’Brien, Dr Todd Gisby, Associate Professor Iain Anderson and other researchers from the Lab, have been working on the artificial muscle generator technology for the past six years.

Artificial muscle, the main component of the generator, is made of a rubbery material that has mechanical properties similar to human muscle and is capable of generating electricity when stretched.

Dr O’Brien says: “The advantage that we have over our competitors is in the small and soft circuitry that we have developed which controls the artificial muscle. Previously, artificial muscle generators were seen as unpractical to power portable electronic devices because they required bulky, rigid and expensive external electronics.”