The Short Circuit

My son is learning C, and I challenged him to write a program that would ask the user for a positive integer, and the program would calculate if the number was prime.  He was able to do it, but during our discussion, I was trying to get him to think about at what number he should stop doing test divides.  But his mind became wedged on a problem after he quickly realized that the you only had to test divide the prospective prime numbers by smaller prime numbers.  Since his program was to calculate if the user-entered prospective prime was actually prime, he thought having a list of primes would be cheating.  He eventually explained what was distracting him, which of course surprised me, given the deep esoteric nature of his thinking.  Anyway, he soon realized he could just use the odd numbers as a compromise for his program, and that stopping at the square root of the prospective prime was sufficient.  Even so, his idea to only use smaller primes to test candidate primes was a great idea (he didn't invent this, but he did invent it independantly, in his head, after only a few minutes thought--which impresses a father.)

Anyway, I ripped off my son's idea, and wrote a program to rapidly enumerate all of  the prime numbers, up to the 250,000th prime number, using  smaller primes to test larger prospective primes.  This was a different problem than the one I assigned my son, but I wanted to put his idea into practice.

The program I wrote takes only a few seconds to enumerate a list of the first 250,000 primes, and write them to two files, one in binary, the other text.  The speed of the program amazes me since my computer is a few years old.  When I worked on such programs when I was in school, they would take much longer to run.  The speed up is mostly due to advances in computer hardware since then, though my son's algorithm does speed things up for equal hardware--I estimate by a factor of 2 for the program below.

Here is a snipped of the last primes generated (complete lists are available for download below):

Number Prime Number
------ ------------
249990 3497617
249991 3497623
249992 3497671
249993 3497713
249994 3497717
249995 3497743
249996 3497759
249997 3497779
249998 3497827
249999 3497849
250000 3497861

As promised, here are links to the first 250000 prime numbers in text format. If possible, please download one of the zipped versions to save bandwidth: 

• The first 250,000 prime numbers in binary format, compressed. (726kB Zipped text recommended)
• The first 250,000 prime numbers in binary format, compressed. (338kB Zipped binary in little endian)
• The first 250,000 prime numbers in text format (3,907kB uncompressed, larger file, not recommended)

And now for the quickly written source code to generate the primes.

/*
 * program to generate primes by testing prospective
 * primes against previously enumerated primes
*/
#include "stdafx.h"
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define DO_FAST 1
#define CONSOLE_OUTPUT 0
#define NUMPRIMES 250000
typedef unsigned long UINT32;
void hit_return_to_continue();
bool is_pp_p(UINT32 *primes, UINT32 npf, UINT32 pp, UINT32 *miu );

int _tmain(int argc, _TCHAR* argv[])
{
  UINT32  primes[NUMPRIMES];
  UINT32  pp;    /* prospective prime */
  UINT32  npf;   /* number of primes found */
  UINT32  miu=0; /* max index used, that is, max indextinto primes ever used to calculate primes */
  UINT32  i;

  /* initialize first two primes and the number of primes found */
  primes[0] = 2;
  primes[1] = 3;
  npf       = 2;

  /* recursively compile the first NUMPRIMES prime numbers, and save them */
  for(pp=primes[1]+2;npf<NUMPRIMES;pp+=2){
    if(is_pp_p(primes,npf,pp,&miu))
		npf++;
  }
  if(CONSOLE_OUTPUT){
    /*
     *print out book keeping regarding maximum index used
     */
    printf("\n");
    printf("The maximum index into the list of prime numbers we\n");
    printf("used to generate the first %ld prime numbers was %ld.\n",NUMPRIMES,miu);
    printf("The prime number at this index is %ld.\n\n",primes[miu]);
    {
      unsigned long long alpp;/* approximately largest prospective prime that we can evaluate using this method */
      alpp=(((unsigned long long)primes[NUMPRIMES-1]*(unsigned long long)primes[NUMPRIMES-1]) - 2)|1;
      printf("The biggest prospective prime we will be able to\n");
      printf("evaluate, using this method and a list of %ld\n",NUMPRIMES);
      printf("prime numbers, will be approximately: %lld.\n\n",alpp);
    }
  }

  /* create txt and binary files of NUMPRIMES prime numbers */
  {
    FILE *fptr_txt=NULL;
    FILE *fptr_bin=NULL;
    fptr_txt=fopen("primes.txt","w");
    fptr_bin=fopen("primes.bin","wb");
    if(fptr_bin==NULL || fptr_txt==NULL){
      printf("Cannot write the files, closing.\n");
      if(fptr_bin!=NULL)
        fclose(fptr_bin);
      if(fptr_txt!=NULL)
        fclose(fptr_txt);
    }else{
      /* write text file */
      for(i=0;i<NUMPRIMES;i++){
        fprintf(fptr_txt,"%6ld %7ld\n",i+1,primes[i]);
      }
      fclose(fptr_txt);
      /* write binary file */
      fwrite(primes,sizeof(UINT32),NUMPRIMES,fptr_bin);
      fclose(fptr_bin);
    }
  }
  /* pause for return for windows run */
  hit_return_to_continue();
  return 0;
}

/* is the prospective prime really prime */
bool is_pp_p(UINT32 *primes, UINT32 npf, UINT32 pp, UINT32 *miu )
{
  bool rval=true;
  UINT32 i;
  UINT32 end;

  /* no need to check primes larger than square root of candidate prime */
  end = (UINT32)sqrt((float)pp);

  /* check to see if the candidate prime is divisable by previous primes */

  if(DO_FAST == 1){
	/* divide by primes */
    for(i=0;primes[i]<=end && rval;i++)
      if(0 == pp%primes[i])
	    rval=false;
  }else{
	/* divide by odd numbers */
    for(i=3;i<=end && rval;i+=2)
      if(0 == pp%i)
        rval=false;
  }

  /* save i if it is greater than previous maximum index used, to keep track index to largest prime used so far */
  if(i > *miu){
    *miu=i;
  if(CONSOLE_OUTPUT )
    printf("New miu=%ld.\n",*miu);
  } 

  if(rval){
    /* we found a prime, save it to our list */
    primes[npf]=pp;
    if(CONSOLE_OUTPUT)
      printf("%6ld, %ld \n",npf+1,pp);
  }
  return rval;
}
void hit_return_to_continue()
{
  printf("\nhit return to continue.\n");
  fflush(stdin);
  getchar();
}

My son is learning how to solve 4x4 and 5x5 cubes, and he noticed some errors in Dan Harris' book, "Speedsolving the Cube:  Easy-to-Follow, Step-by-Step Instructions for Many Popular 3-D puzzles."

The book has an errata, but the website where the errata was published is down and has been for some time.  So I am going to republish it here, for the benefit of others who may have the book and no list of errors.
Read more...

Electrical engineering rules of thumb (EEROTs) are time saving design guidelines used by electrical engineers.  However, not all EEROTs are created equal, and many are not timeless.   I have witnessed engineers, including myself, blindly apply EEROTs, only to regret it the morning after. 

This raises the question:  how does a young electrical engineer know when to use an especially alluring rule of thumb?  The answer is:  one must keep in mind not only the EEROT, but also its rationale.

Here, we begin what will hopefully be the first in a series of posts discussing various EEROTs.

Old EEROT #1: Do not use signal initializations in synthesizable code

Signal initilization in synthesizable VHDL to initialize registers used to be a cardinal sin because initialization was simulatable but not sythesizable.  What this means is it would behave one way in simulation, but infer logic that did not behave the same way in practice.  This led to behavioral discrepancies between simulation and hardware.  Consequently, a popular EEROT used to be "do not use signal initialization in synthesizable code." 

For example, Ben Cohen, in VHDL coding styles and methodologies, wrote "initialization is ignored by sythesizers".^{(Cohen 1999, p. 119)}  To be fair, Mr. Cohen's advice is still correct when targeting ASICs, and it was probably valid for FPGAs back in 1999, but FPGA synthesizers have evolved since then, and no longer universally ignore initializations when initialized signals infer registers.

Specifically, in addition to the connections among registers and the specification of combinatorial logic, FPGAs, unlike most if not all ASICs, have an innate capacity to provision the values registers contain immediately after configuration, independent of reset.

In response, FPGA synthesizers initially provided out-of-band mechanisms to specify the after-configuration value of registers.  One such mechanism took advantage of VHDL's ability to specify user defined attributes.  In the following (now depreciated) example, based on XST, a VHDL user defined attribute init is applied to my_reg, in order to control its value upon exiting FPGA configuration:

Read more...

James Clerk Maxwell

In a segment on James Clerk Maxwell, the Nature podcast narrator begins at 22:29:

A hundred and fifty years ago this month, a 30 year old Scotsman called James Clerk Maxwell wrote down the four equations that made him famous.^{(Nature 2011)}

One problem with Nature's introduction is Maxwell's equations did not make him famous, initially.  Another is he did not write down four equations; he wrote down twenty.  It was Oliver Heaviside who simplified Maxwell's equations to the four equations we know and love (or loathe) today, as is documented in two biographies by Basil Mahon: one on James Clerk Maxwell, and the other on Oliver Heaviside.^{(Mahoon 2004, 2009)} Wikipedia also has this documented if you do not have access to the books.
Read more...

Just some hack code I threw together for evalating the Josephus Problem.

The Josephus problem described in Concrete Mathematics can be stated in an equivalent yet family friendly form as follows: n players stand in a circle to play a game of “Josephus tag”. When the game starts, the first player tags the second player, and then the third person tags the fourth, and so on and so forth. When a player is tagged, he is out. After the first round, subsequent rounds ensue until the last survivor, who declares herself the winner.

For a game with n players, which position should one select to ensure survival and hence victory?

This program will spew the order of the players who are out in reverse order, allowing you to analyze the results in an effort to find patterns for the last survivor, the second to the last survivor, and so on. For exmaple, here are the rusults for the Josephus problem with 2 through 9 players. Looking at the n=9 case, player 3 is the winner, while player 7 was the last to be tagged.

Reverse Order Out    2:     1    2
Reverse Order Out    3:     3    1    2
Reverse Order Out    4:     1    3    4    2
Reverse Order Out    5:     3    5    1    4    2
Reverse Order Out    6:     5    1    3    6    4    2
Reverse Order Out    7:     7    3    5    1    6    4    2
Reverse Order Out    8:     1    5    7    3    8    6    4    2
Reverse Order Out    9:     3    7    9    5    1    8    6    4    2

Source code is below the fold. As always, for legal reasons, it is provided as is.

Read more...

Please see other post.

My 9 year old son Alexander came up with a couple of closed form solutions to the Joesphus problem.  Really.  If this helps you, please leave a comment, he will enjoy it.

 A discussion of his solution (conjectures) and an attempted proof by me of one of them can be found as the first link in the references.

His main conjecture is:

$J(n)=2(n-2^{\lfloor\log_2 n \rfloor})+1, \mbox{ for } {n} \ge {1}$

where

$floor(x)=\lfloor{x}\rfloor$

is the largest integer not greater than x.
Read more...

The circuit in figure 1 is useful for passing pulses across ascynchronous clock domains. Its purpose is to convert a pulse in one clock domain to another clock domain, while mitigating metastability inherant in clock domains crossing (CDC).⁽¹⁾ VHDL source code can be found below. 

For our purposes, a pulse is defined as a synchronous signal one clock period in duration. Pulses may be used to load registers, or to indicate status such as "output valid", as two examples. When passing busses from one clock domain to another, resynchronized pulses may be utilized to ensure that all bits in a data bus are stable in the destination domain before being used as valid data. 

Figure 1: Circuit for passing pulse across clock domains

Theory of circuit

A pulse is converted to state change with a T flip flop, TFF0. The state change is synchronized to the destination clock domain via two cascaded D flip flops (DFFs), DFF0 and DFF1. The output of DFF1 is cascaded to DFF2, where the input and output of DFF2 are exclusived ORed to create a pulse in the destination clock domain. 

Detailed explanation of circuit 

Read more...

Old news, but I was quoted by Ron Wilson for an article in EDN. The topic was power estimation for FPGAs. Before the interview, I made a deal with my boss that if Mr. Wilson quoted me in his article, I'd get an office with a door.

It was flattering to be quoted, but I didn't get the office.
Links

• Wilson, Ron (04-23-2009) Power fortunes: Estimating power in FPGA designs EDN

Bruce Schneier’s Blowfish was mentioned again on 24. This time, a character on 24 claimed that the designer of the algorithm put in a backdoor.

Blowfish is neat little encryption algorithm designed in the mid 1990s by Bruce Schneier. I first came across it in the April 1994 issue of Dr. Dobb's Journal, a magazine for working computer programmers and hobbyists.

The magazine ran an associated contest to crack blowfish, and I naively took the bait. The deadline passed without success.  But soon thereafter, I discovered a problem with the C-source code implementation: a sign extension bug.

Specifically, a key in blowfish was represented as array of char in the early C-source implementations.  A char is a type in the C language.   The C language doesn't specify whether chars are supposed to be treated as  signed or unsigned.  However, many compilers treat chars as signed by default,  unless the programmer explicitly declares or casts the char as unsigned.

Read more...