Summer is not enough to redistrict

      Summer went by really fast. I was busy enough with other problems. Since my blog doesn’t really have an audience, it is more like a diary to be reread someday.   A relative of mine peeked at it.

         I downloaded census and other data for Arizona. I compiled code I wrote in Fortran.  Sorting latitudes into bins seems to work, and I recommend that approach.

     Everybody insists that districts must be contiguous, but nobody publishes a table of adjacent census blocks.  Creating a table for adjacent census blocks was very time-consuming. I tried to create a table with eight columns. Columns 1 through seven were for data, and column 8 was a pointer to more data in case of more than seven sides to a census block. LOGRECNO could be a four byte integer, whereas the GEOID could not. Each row was for the LOGRECNO of a census block. The data in the row was the LOGRECNO of all adjacent census blocks. After the data, the next column in the row is a zero to signal the end of the data. NANs or undefineds are not allowed in the table.  I expected that few census blocks would have more than seven adjacent neighbors.

      Results were poor.  A few sides seem to have the same census block on both sides.  Also, some census blocks apparently had dozens of adjacent census blocks.  It is easier for me to believe these anomalies are errors in the census data, instead of admitting that these anomalies are due to my buggy code.  It was a stretch to extract the necessary data and trapeze all the way from sides to faces to GEOIDs to LOGRECNOs.  The trapeze apparently dropped some data along the way.   Sandboxwalls juggled the data yet again to match the latitudes and longitudes in the bins before putting the data into an internal eight column array for its use.

      It would have been nice if someone else had published such a table of adjacent census blocks. The GIS companies being well-funded by the politicians have staff available to extract this sort of data for their gerrymanders. I suppose the excuse for nobody publishing such a table is that there aren’t that many people attempting to create software to do automated redistricting. This people, however, needs all the help he can get. 

     In Sandboxwalls, when the district seed balloons into another district balloon, vector forces are created. The vector forces accumulate, but are all released at the same time. Having the release at intervals of population increase seem to work better than having a release caused by various events. It can consume a fair amount of time for the vectors to move the district centers to their new positions and re-create the arrays. Wall height was determined such that the effective eccentricity of district to city to County radius was 1 to 2 to 3. When the sand overflowed a wall, a new radius was created at the point of overflow. I never got a complete result, but did expand far enough that the population difference between all districts was under 1%. Some districts expanded to their maximum radius.  I suspect that was not because the district was hemmed in by other districts, an eventuality for which I was prepared. I am afraid it was because of too many holes in the adjacent census blocks data.   I ran out of time before I had a chance to investigate this.   I never did create a dotCSV file for a 30 district map of Arizona.

      Time to forget about redistricting by computer, and get ready to help put on the upcoming consolidated elections November 8.  After that, well, summer vacation is over, so playtime is over.  Maybe next year if I can afford it.

Sorting the census blocks for redistricting

 

Another method for sorting the census data for redistricting has occurred to me. Back in ancient times, there were machines that could sort punch cards. See: http://en.wikipedia.org/wiki/IBM_80_series_Card_Sorters.  For example, cards could be sorted into ranges of latitude. The cards would be conveyed horizontally until they dropped into the proper bin below.  Today, the same sort of thing can be done in software, known as a radix sort. This could be faster than even the merge sort that I was considering, and the code could be more compact as well. I hadn’t considered radix sort seriously before, since potentially a huge memory would be required. I remember monolithic 2K byte chips, so half  gigabyte memories are huge to me. Ancient FORTRAN required arrays to be dimensioned at the beginning of the software program.  Today, modern FORTRAN allows calculating efficient dimensions for the array before allocating memory to the array.  The old way would have been to use a linear array and then calculate the 2 dimensional subscripts for that array. 

 I intend to write code for a radix type  sort to separate the census blocks into stripes of latitude ranges.  The census blocks in each stripe can then be sorted by longitude.  Merge sort will hopefully work well enough for the stripes.  Other methods of sorting may be faster, but I doubt it is worth my time to code them. After all, the goal is redistricting by computer. I have already learned way too much about sorting, but help is not on the way.  I am still writing code and haven’t started debugging.  A compile now and then reveals tons of errors that are easily fixed.

bug is i=1 was shifted left a column

Decades ago, some academics tried computerized redistricting by growing districts from a seed.  Sandboxwalls also grows districts from a seed.   Even though that research was paid for by taxpayer dollars, that information is inaccessible,  stuck up in ivory towers.  I imagine those experiments mostly failed, as researchers after that pursued instead the heuristic methods for redistricting.   Circles don’t fit together well, but I’m hoping my experiment with sandboxwalls will do better.  Time will tell, but spare time is hard to come by. I envy the several contestant teams in the state of Virginia. Each team had over half a dozen undergraduates and a faculty advisor. The good news is that slowly more people are doing redistricting. Unfortunately, gerrymandering is still the clear winner.

Closs Enuf 4 Govment Work

  For redistricting, random processes should not be used.  Certain software given the identical census data run on a compatible computer should yield identical results.  That way all parties can verify that the results are not just something cooked up in a smoke filled room.  If the results from different computers aren’t precisely identical, careful analysis will reveal the cause of the discrepancy.  This is better than an independent redistricting commission.  A commissioner is likely to know that San Francisco is liberal and Orange County is conservative.  Even dissecting the brain of a commissioner will not reveal if that knowledge or some other knowledge improperly biased a decision.

 There has always been a trade-off in computing between accuracy and speed.  Double precision takes longer to calculate than single precision.  Consider finding the closer of two points to a center.  If the distance to the two points is almost identical, then greater precision is required to resolve which is closer.   If using 64 bit integers, the squares of each distance can be compared instead of the distances themselves.  Since I am using a borrowed six-year-old home computer, approximations and shortcuts will keep the running time reasonable.  There is always the danger that not being precise enough will result in an incorrect comparison.  A way to save the situation is to measure how identical the distances are.  If too close to identical, the calculation can be redone with higher precision and without so many approximations.  Hopefully, this should rarely happen.  Still, it takes more time to measure how identical, recalculation or not.   Until I actually run some software, I won’t know how long a time is needed for any of this.

 There is no cure for the worst-case scenario.  More cosine terms could always be used, and more decimal places in Pi could forever be added without limit.  I didn’t like the idea of a hidden MSB bit, but IEEE 754 is crucial for portability of software among computers.  Still, there comes a point where the results should be accepted if they were fairly generated.  In gambling lotteries, we analyze the fairness of the selection process, not the precision of the results.  In gerrymandering, the end results justify any shady means.

It is time for me to prepare for the incoming data.  No, not the census block data, but instead, my W-2’s and 1099’s must be collected.  My taxes are unpredictable, as I haven’t figured out yet what Congress has done to us taxpayers this time.  I will have to do my taxes before I can attempt to do  SandBoxWalls to Congress.
 

Some Census data will be released next month. I doubt I will be ready in time.

Out of Sorts with Redistricting

      My ideas for redistricting with a sandboxwalls program involve a lot of data sorting.  First, the census blocks of a state are sorted by latitude.  However, the states are two dimensional, not one-dimensional.  Consider a television picture.  The picture is made up of horizontal stripes.  Using that concept, the latitude of the State is then divided up into stripes.  The census blocks within each stripe are then sorted by longitude.  A box is placed on the picture.  The center of the box is where a district will grow outward in all directions from a dot.  The box then contains segments from a number of horizontal stripes.  All of the census blocks within the box must be sorted by distance from the center dot.  That way, the district can grow by acquiring the closest census blocks in order by distance.  See my last blog on the square root.  To keep all of the districts at about the same population, a tally records the current population for each and every growing district.  The district with the lowest population grows by acquiring a census block.  To know which district has the lowest population, the tally must be kept sorted by population.  To correlate PL94-171 data with Shapefiles data, they can both be sorted to match.
      To get this far has involved a lot of sorting.  If the census blocks are delivered by the Census Bureau in some kind of order, that can either be a help or even severely hinder depending on the order versus the chosen sorting algorithm.  I call the order seemingly being used as “thoughtlessly random”, and chose accordingly.  How to implement all this sorting is a job for a software engineer.  Unfortunately, I have never found a software engineer interested in playing with my sandboxwalls.
      After some thought, I realized that the classic bubble sort algorithm should work well for sorting the tally each time.  But bubble sort would be horribly time consuming at sorting a state’s amount of census blocks by latitude, and a different sorting algorithm is clearly needed there.  I use a binary search insertion sort algorithm for that.
      Actually, there isn’t exactly a best sorting algorithm for a given sorting problem.  My analysis of the sorting the box problem resulted in a solution that is a combination of algorithms.  Each segment in the box is split into 2 pieces. Each piece becomes a list which is then bubble sorted.  The 2 lists are then merge sorted into a single list.  Each merge sorted list is then binary search insertion sorted as a batch of census blocks into the final result.  This requires more than the usual amount of code of course, but it is the quickest way I know how to get the result.  I hope it will work.
      The public library eventually got me the book I put on hold.  The title is “The Art of Computer Programming volume 3″ by Donald E. Knuth.  I learned several things about sorting from this book.  Much of what was discussed is over my head, as the subject of sorting has depth.  I already knew that I needed help, but the book is the best help I have been able to get.  Also, it seems that some version of the merge sort algorithm is more appropriate for quickly sorting the census blocks by latitude than what I have now.
      The question is: Do I have enough time to go back and rewrite the FORTRAN, or would it be better to spend the time attempting to debug what I have now?  The reality is that I still have no idea how to extract the data needed for redistricting from the big knotted clump of data supplied by the Census Bureau for gerrymandering.  I may be limited to rectangular states if I am unable to obtain the data or figure out how to use the TIGER Shapefiles to limit the length of horizontal stripes to within a state border.
      The Holidays are almost over, and soon I will be back to earning a living instead of playing with FORTRAN programming for redistricting.  Happy New Year seems like a wish, not a reality in this economy.  When I get a chance, the next blog will be about accuracy.

Faster than a speeding square root

In the data from the Census Bureau, the location of the census blocks are given by latitude and longitude. Instead of degrees, minutes, and seconds, the latitude and longitude are given in millionths of a degree. Fortunately, these are conveniently expressed as 32-bit integers. Finding the geographical distance between two points usually means employing the Pythagorean theorem by the computer. But if fast is desired and sloppy is acceptable, the square root can be avoided. The first method is to simply add a horizontal “X” distance to the vertical “Y” distance to yield an approximate hypotenuse. This first method is three times faster than the Pythagorean theorem, but the error is up to 42%. One reason for the great speed is no need for a squared term, which could overrange the integer. Another reason is that square root requires floating point values.

 For Sandboxwalls in the early stages, all of the census blocks near the district center will be included in the district anyway. The order in which they are included is unimportant. In spite of the sloppiness, the result is the same. In the late stages of the Sandboxwalls algorithm, such sloppiness would cause some census blocks to wind up with a different district. Although the Pythagorean theorem is needed in the end, the Sandboxwalls algorithm can be speeded up by not using square root in the beginning. The trade-off is how much speed is achieved for an allowed sloppiness.

 A second method works as follows: take the shorter of “X” and “Y”, and cut it in half. Add that half to the longer of “X” and “Y” to yield an approximate hypotenuse. Although taking a little more computer time, the error is 0% to 12%. Although taking half is a division operation, an optimized compiler will accomplish this quickly with a shift register operation. Keeping in mind the need to use shift register operations, method three subtracts an additional term. Besides the half of the shorter of “X” and “Y”, a 16th of the shorter is also subtracted. Method three is still almost twice as fast as using the Pythagorean theorem, and the error is 0% to 9.2%.

Method 4 subtracts an eighth instead of a 16th. The speed is the same but the error becomes from -2.8% to about 7%. Method Five is an attempt to get the best of both Method three and method Four. Mostly method five uses method three, but switches to method Four if the angle is large. The error for method Five is 0% to 7%, but the price for the greater accuracy is much less speed.

 I wondered if the quick values obtained by one of these methods could be used as the initial value in the Newton Raphson algorithm for square roots. Unfortunately, this algorithm consumes more computer time using Fortran than the standard optimized Pythagorean theorem.

Here is a chart of my results:

Method 1: long + short integers                                78 time units      error:  0%  to  42%
Method 2: long + half short integers                         94 time units      error:  0%  to  12%
Method 3: long + half short – sixteenth short         156 time units      error:  0%  to  9.2%
Method 4: long + half short – eighth short              156 time units      error: -3%  to   7%
Method 5: long + switch sixteenth,eighth                203 time units      error:  0%  to   7%
Pythagorean: single precision square root               281 time units      assumed accurate

This is the fortran code cut from a test program using method 5:

       i=kx*(longmz-longsf);  j=ky*(latmz-latsf) !-Martinez
       if(i<j) then                             
          if(8*i<7*j) then   !–used 7/8 ratio since 8=2^3
               id=j+i/2-i/8
          else
               id=j+i/2-i/16
          endif 
       else
          if(7*i>8*j) then
               id=i+j/2-j/8
          else
               id=i+j/2-j/16
          endif
       endif

Another time consuming process is sorting the census blocks. I’ll consider that in my next blog.

Make my districts contiguous please

In redistricting, contiguous is a fancy word meaning the district is one lump without any loose flakes floating around. If a district includes part of a county, I see  no reason for that district to have little pieces of that county that are unconnected with the main part of the district. This assumes that the county was contiguous. Consider a city that is not contiguous, since it has small unconnected parcels of land. If a district includes part of that city, then perhaps that district has a valid excuse to not be contiguous if that district includes some of those small unconnected parcels of land.

For sandboxwalls to keep districts contiguous, before adding a particular census block to the district, it must  confirm that the particular census block is adjacent to the district. This could be done by checking a contiguous blocks table with records as follows:
The first integer identifies the particular census block. The next integers identify the census blocks adjacent to the particular census block. In the rest of the record the integers are padded with a zero.   Every census block would have a record, and the records would be in a searchable order.   Such a table would allow the software to verify that no district has unconnected fragments. 

Such a table could I presume be constructed from data in the census TIGER files. I looked at the following website.

http://www.census.gov/geo/www/tiger/tgrshp2008/ats2008ch3.txt

3.9.1.1            All Lines Shapefile Record Layout

            The shapefile name is: tl_2008__edges.shp

            The shapefile is county-based.

            The following is the shapefile’s attribute table layout:

Field   Length            Type    Description

STATEFP      2          String  Current state FIPS code

COUNTYFP   3          String  Current county FIPS code

TLID    10        Integer            Permanent edge ID

TFIDL 10        Integer            Permanent face ID on the left of the edge

TFIDR 10        Integer            Permanent face ID on the right of the edge

When they say they edge, I presume they mean a segment of the polygon that is the perimeter of a census block. I have no idea how to take the Permanent face ID and get a latitude and longitude of that census block. The census files are usually massive and  are geared for use by States and large companies, not hobbyists.  I have not attempted to download any of them. It is important enough to me to have such a table.  If desperate I could create a fake table that had a certain number of the nearest districts, even if they weren’t adjacent. Nearest could be determined by using latitude and longitude of the census blocks.  Hopefully someone can give me clues on how to construct an Adjacent Blocks Table.

To find the distance from a district center to the census block, do the following:
Subtract the longitude of the district center from the longitude of the census block to get horizontal distance X. Next, subtract the latitude of the district center from the latitude of the census block to get the vertical distance Y.  Since X and Y are on planet Earth instead of a flat surface, they must be multiplied by correction factors. To save computation time, sandboxwalls does not calculate the correction factors for every distance. That requires cosines. Instead, the correction factors are calculated for each district center and those are used repeatedly as an approximation. Now take the corrected X and Y and use the Pythagorean theorem. The hypotenuse is equal to the square root of the sum of the squares of X and Y.

Unfortunately, that means to find every distance requires a square root function. To save computation time, in my next blog I try a sloppy but fast way to find square root.

Redistricting on the Internet

The World Wide Web meant easy access to previously hidden information. No longer was it necessary to hunt through libraries to find information on unusual subjects, such as redistricting. I found that there were a few others out there currently pursuing computerized redistricting. Better yet, blogging offers the chance to make my findings available to the world. But the hope of finding others to help me in my pursuit of redistricting has not happened. Academic libraries don’t make all their materials available to the public, even though their research is funded by taxpayer dollars. What I have seen from the Ivory Tower is about how computerized redistricting is such a difficult problem to solve. Nothing about how to download and use the census data.

Over the decades, I have reached some different conclusions from  others in this niche. I consider it impractical to achieve some perfect redistricting plan. The gerrymanderers can simply have the computer analyze millions of plans to find one that steals the most votes in their favor. I reject the idea that there is a comparable easy measurement that measures the ” goodness” of a redistricting plan. A minimum district perimeter plan does not take into account the city and county boundaries, which I consider to be a terrible weakness. There is no perfect value of how much account should be taken. The values I have chosen are a bit arbitrary. Experimentation will reveal whether or not the chosen value is practical. Too little account would lead to a redistricting plan similar to that created by a minimum district perimeter algorithm. Too much account could lead to stretched out uneven districts, though I doubt they would look as brutally mangled as typical gerrymandered districts. The trick then would be to get a consensus on a practical value that could be enacted into law.

Simulated Annealing redistricting is too heuristic for me. Splitline redistricting is another algorithm which I consider to be a competitor. It ignores census blocks in favor of smooth straight lines. Sandboxwalls grows districts from a seed. Originally, the idea was to plant the seed in the center of the existing districts. Unfortunately, the present existing districts are mangled by gerrymandering. Thus, an awful lot of evolution would be required by Sandboxwalls to produce good districts from bad. It has occurred to me to start with something better than such mangled districts. A lot of time could be saved by planting the seed in the center of each of the Splitline districts. I have no idea how to get the latitude and longitude out of the Splitline districts. Even if I did, I am not interested in a fight with whoever or whatever owns Splitline.

But experimentation is a long way off. Concepts have to be turned into working FORTRAN code. That takes time, and staying employed is more important than playing with lost causes like computerized redistricting. Somehow data has to be extracted from the Census Bureau files. In my next blog, I will ask for clues on how to do this.

The Joy and Toll of Moore’s Law

Redistricting was also affected by Moore’s Law.  I saw no reason that Gordon Moore’s prediction should be a law, as I saw it as a mere coincidence that would be temporarily true. I still don’t understand why Moore’s Law is true, but I was obviously wrong about it being temporary.  The result of ever increasing computer power was not just that a computer could win a chess game.   Somehow, the promise of more computing power on everyone’s desktop (even mine!) didn’t mean I had the computer power to do automated redistricting.  The reality was major gains for gerrymandering.   It gave those who gerrymander an increasingly powerful tool.  By having the Census Bureau include voter districts, the GIS companies could more accurately correlate voter data with census data.  The addition of voter data made gerrymandering software stunningly accurate, so that most incumbant candidates for district office won before the first vote was cast.

Politicians have strained to ignore that a computer can do redistricting.  Ironically, the precision of gerrymandering  is made possible by gerrymandering software.  Redistricting software is limited to curious academic research and hobbyists, even though gerrymandering software is more difficult to write since it must also include voter registration data.  The difference is that gerrymandering software is profitable, since there is a strong demand for it from politicians.  Thanks to increased computer power, the purchase price of a safe seat is way less than the cost of an election campaign.

 Another problem was the fragility of software.  If the software is to be widely understood, a high level language is needed.   More powerful computers were an excuse to upgrade software, making previous software obsolete.  Digital decay and data rot set in.  BASIC went from MSBASIC to QBASIC to VBASIC which demonstrated a problem for redistricting software. A decade from now, software written today could be useless just because of a language change.  If a computer program to do redistricting is actually used, it would have to be backed by law. What was needed was a computer language would be stable for decades, not merely years.   Otherwise, the law would be useless as the computer program it was based on couldn’t be run in the future.   I decided to abandon BASIC in favor of FORTRAN for that reason.  FORTRAN isn’t dependent on a particular operating system.  It  runs on open source operating systems which are more stable as well.  Of course, FORTRAN is out of the mainstream where obscuring the software code contributes to profits.  And yes, FORTRAN has been around so long that many FORTRAN programmers are now in graveyards.

But the huge increase in computer power was just one revolution, and  Moore’s law says that revolution will continue.  But another bigger revolution is my next topic.

From Bubbles to Sand

Redistricting based on soap bubbles wasn’t good enough. Finite element analysis to simulate surface tension of the bubbles was too computationally intensive. Such redistricting also did not take into account county or city boundaries. Although the starting and growing from a seed point seemed correct, a better apportioning method was needed.

I considered a pile of sand. If the sand was coming from a funnel in the sky, it would fall to the surface and form a cone. The base of the cone would grow in a circular manner similar to the soap bubble analogy. Instead of a completely flat surface, consider what would happen if there was a wall wherever there was a county or city boundary. The sand would hit the wall and stop expanding there, causing the base of the sandpile to assume the shape of the boundary. Eventually, the sandpile would overflow the wall and start filling the next compartment. Software using this analogy could grow districts in a compact manner, but also take into account the county and city boundaries. The key question then was how high the wall should be. After much thought, I concluded that what was really desired was districts with a set maximum value of eccentricity. For example, a city could have its wall low enough that the widest part of the base would not exceed double the narrowest part for an eccentricity of two. County walls would be higher with an eccentricity not exceeding three.  It is easy to visualize a sandbox with slightly higher walls for county boundaries, and within those county boundaries are slightly lower walls for city boundaries. Sand falling from the funnel in the sky still has a roughly circular base, but modified by the wall boundaries. The eccentricity determines that roughness.

With software we don’t have to strictly follow the model of our physical world. When a particular cone of sand reaches a wall, the height of the wall can be set for the desired eccentricity. If a different cone of sand reaches the other side of the same wall, a different height will be computed. Thus, the inside of the wall will have a different height from the outside of the wall. For those who demand an analogy, see the explanation for TARDIS in the Dr. Who episode “Robots of Death” from the BBC.

One of the nice things about soap bubbles was that they would push away from each other on contact. To keep this nicety, when two sand piles touch, vector forces can move the sky funnels away from each other. Actually the software would keep the funnels fixed in place while the vector forces accumulate, and then all the funnels would move to their new location at the same time.  The movement would be triggered by events, such as the program having assigned to districts a certain percentage of the State’s population.

But time marches on, bringing progress both good and bad whether we want it or not. The next computer revolution changed everything yet again.

How I Got Interested

     Back in ancient times when I was in college, I was taking a couple of very different courses.  One course was Computer Science, where I learned a computer language called Fortran II-D.  Yes, that’s II meaning two in Roman Numerals, it was that long ago.  The other course was Political Science, where I learned about ReDistricting.  It occurred to me that someday computers could do ReDistricting.  My PolySci Professor pointed out to me where in the textbook it said that because there were so many possible combinations, it would be impossible for a computer to do ReDistricting.  That same sort of argument also explained why a computer could never hope to play a winning game of chess.  True enough in those ancient times.
    Back then, my thought was having the computer start each district growing from a spot.  The district would expand by acquiring the nearest blocks.  By keeping a tally of the population of each district, the district with the lowest population would grow next.  That way, the population of all the districts would stay roughly equal as they grew.
    The districts would eventually grow into each other.  Some sort of apportioning process was needed.  The vision I had was of soap bubbles.  You have to try playing with bubbles  to really see their beauty.  Bubbles of different sizes form a membrane between themselves in an almost magical manner.  By carefully inserting a small straw into a bubble, you can blow into the bubble to enlarge it, or suck out some of the air to make it smaller.  Imagine instead of 3 dimensional bubbles, you could make 2 dimensional bubbles.  Place those bubbles on top of a map of the State, with each bubble being a district.  The membranes between the bubbles would form the ReDistricting boundaries.  Magical indeed!
    I was surprised that I could find no one that had any interest at all in trying to ReDistrict by computer.  I could understand why politicians would have no interest, but academics and software writers also had no interest.  This was a puzzle that I didn’t have the pieces to solve, much less a mainframe, so I quit thinking about it.
    Then a new revolution happened.  The Personal Computer, or PC was born.  I taught myself a new computer language called BASIC, which was serving me well with other puzzles.  It was a long time before I reconsidered the ReDistricting puzzle.  But, yes, I finally did. 

Follow

Get every new post delivered to your Inbox.