Modular Mathematics

A friend had a question to determine the largest integer divisor that would yield the same integer remainder for three given integer values. The provided example problem was not too difficult to solve by inspection, but I wanted to know the "why" behind it (and to know that I was correct without writing a quick bit of code to prove it). If you're interested, the three given values were 364, 414, 539. 


It's tempting to start with prime factoring, but that is not the path to success in this case, at least not yet...

After spending quite some time staring at and playing with numbers, we figured out how to solve for a special case where b > a > b/2. In that case, the greatest modulus always appeared to be (b-a). But, this broke down if a < b/2. An example we used was 353, 262, and 54.  353-262 = 91. 


Checking the answer: 353 / 91 = 3 + 80/91   and 262 / 91 = 2 + 80/91


Great, but 262 - 54 = 208, so now what...  Sure it "works" with 262 = 1 + 54/208 and 54 / 208 = 0 + itself. But, not a useful exercise for the general problem.

Then we got close to the answer, looking at the intervals but not seeing their relationship, here's a teaser:

353  - 262 = 91
353 - 54 = 299
262 - 54 = 208

We were close, but got distracted because we are well trained to factor the starting vales.  I postulated that we should pull out additional multiples of 54 and see what happened.  

353 - (6 * 54) = 29 
262 - (4 * 54)  = 46


This was as big of a red herring as factoring the values themselves. We care about the bloody remainder, but if we factor, it's zero and the answer is pretty boring. It was hard to get out of this box. In our special case where b > a > b/2, it was always true that b mod (b-a) and a mod (b-a) were congruent, the following was also true in this case:


(b / (b-a)) - (a / (b-a)) = 1

In retrospect, this seems obvious, as it quickly decomposes to an identity relationship: b-a clearly equals b-a.

-=-=-=-=-=-=-=-

The benefit was that I then realized that the congruency should hold if (b/m) - (a/m) = n, where n is any integer. (And similarly, if there are three numbers c > b > a, then c/m - b/m = i and c/m - a/m = j must also be true, where i and j are also integers). 

Rephrasing using a modulo function, a mod(m) must be congruent to (a + mi) mod(m) for any integer i.


So, If b can be expressed as (a+mi), then the common modulus will be m. This means that the greatest common divisor associated with the intervals we calculated must be my modulus. So, we need to factor 91, 299, and 208: 

91 = 7 * 13 
208 = 2^4 * 13 
299 = 13 * 23



13 is the only common factor, and therefore the GCD, and therefore my modulus. Testing this solution:



353 / 13 = 27 + 2/13
262 / 13 = 20 + 2/13
54 / 13 = 4 + 2/13

Applying this methodology to the original problem:

539 - 414 = 125 = 5^3
539 - 364 = 175 = 5^2 * 7
414 - 364 = 50 = 2 * 5^2
The GCD is therefore 5^2 (aka 25) and the remainder is clearly 14 by simple inspection.




    

My 2nd Hunk of Python Code

Build (potentially useless) NMEA data from MOTOACTV downloaded CSV file:

---

Acknowledgement: thanks to Beni Hess' comment on a Python Recipe post for saving me days of trying to figure out the XORs for the checksums.

Also, this NMEA reference from Robosoft proved helpful in building the sentences.

Updated below, now that all the calculations are set up as functions. Final version is posted here.

---

#!/usr/bin/env python

import csv, time, math, operator

filename = "rawDataCsv.csv"

# filename = "miniDataCsv.csv"

# Recorded epoch is GMT, staticly setting this to CDT for now

TZoffset_hours = int(-5)

# Living without minute offsets and assuming zero

TZoffset_string = str(TZoffset_hours) + ",00"

# Function to generate time (to the second, with truncated hundredths -- close enough) and date from the recorded timestamp

def Epoch2DateTimeStrings(epoch):

    noms_epoch = str(epoch)[:-3]

    just_ms = str(epoch)[-3:]

    cut_epoch = float(noms_epoch)

    HHMMSS = time.strftime("%H%M%S",time.gmtime(cut_epoch))

    DDMMYYYY = time.strftime("%d,%m,%Y",time.gmtime(cut_epoch))

    hundredths = str(just_ms)[:2]

    time_string = str(HHMMSS) + "." + hundredths

    date_string = str(DDMMYYYY)

    return (date_string, time_string)

# Function to determine the cardinality of a coordinate (lat/long), based on its sign (+/-)

def Cardinality(coordinate, latlong):

    if latlong == "longitude":

        if coordinate < 0: cardinality = "W"

        else: cardinality = "E"

    elif latlong == "latitude":

        if coordinate < 0: cardinality = "S"

        else: cardinality = "N"

    return cardinality

# Function to convert a coordinate (lat/long) from decimal degrees to degrees and decimal minutes

def Deg2DegMin(coordinate):

    coord = math.modf(math.fabs(coordinate))

    coord_deg = int(coord[1])

    coord_min = float(coord[0] * 60)

    return (coord_deg, coord_min)

# Function to convert Latitude and Longitude to NMEA GLL format

def LatLong2Strings (latitude, longitude):

    latitude_direction = Cardinality(latitude, "latitude")

    longitude_direction = Cardinality(longitude, "longitude")

    # Latitude

    deg_lat, min_lat = Deg2DegMin(latitude)

    deg_lat = str(deg_lat)

    min_lat = str("%.4f" % min_lat)

    lat_string = deg_lat + min_lat + "," + latitude_direction + ","

    # Longitude

    deg_long, min_long = Deg2DegMin(longitude_decdeg)

    deg_long = str(deg_long)

    min_long = str("%.4f" % min_long)

    long_string = deg_long + min_long + "," + longitude_direction + ","

    # Return the strings

    return (lat_string, long_string)

def BuildNMEA(lat_string, long_string, time_string, date_string, TZoffset_string):

    # Concatenate the pieces into the sections of the NMEA GLL and ZDA sentences that get checksummed (omit the leading $ and trailing *ck)

    gpgll_string = str("GPGLL," + lat_string + long_string + time_string + ",A")

    gpzda_string = str("GPZDA," + time_string + "," + date_string + "," + TZoffset_string)

    # Calculate the checksums (just in case)

    GLL_checksum = reduce(operator.xor, (ord(c) for c in gpgll_string), 0)

    ZDA_checksum = reduce(operator.xor, (ord(c) for c in gpzda_string), 0)

    # Convert to Hex (no 0x) and pad a leading zero if needed

    GLL_hex = ("%X" % GLL_checksum).zfill(2)

    ZDA_hex = ("%X" % ZDA_checksum).zfill(2)

    # Now, put it all together into a full NMEA GLL and ZDA sentences and render them

    NMEA_GLL_sentence = str("$" + gpgll_string + "*" + GLL_hex)

    NMEA_ZDA_sentence = str("$" + gpzda_string + "*" + ZDA_hex)

    # Return the sentences

    return (NMEA_ZDA_sentence, NMEA_GLL_sentence)

ACTVdatafile = open(filename,"rb")

ACTVdata = csv.reader(ACTVdatafile)

rowindex = 0

for row in ACTVdata:

    # Don't try to grok the heading row from the CSV file

    if rowindex == 0: pass

    # Build NMEA sentences from every other row

    else:

        latitude_decdeg = float(row[5])

        ms_epoch = row[9]

        longitude_decdeg = float(row[15])

        date_string, time_string = Epoch2DateTimeStrings(ms_epoch)

        lat_string, long_string = LatLong2Strings(latitude_decdeg, longitude_decdeg)

        NMEA_ZDA, NMEA_GLL = BuildNMEA(lat_string, long_string, time_string, date_string, TZoffset_string)

        print NMEA_ZDA

        print NMEA_GLL  

    rowindex += 1           

ACTVdatafile.close()

Functions, Expressions, Formulae, and the Like

Last weekend, I participated in a lively philosophical discussion about the nature of functions. We were on the right track, but got derailed by semantics -- particularly because we didn't fully establish the concept of range, and only dusted lightly upon the concept of domain.

My friend had the basic definition right, but we were struggling with the mapping rules because we hadn't established the underlying criteria successfully. My friend correctly argued that simply restating the formula for a circle, such as x^2+y^2=r^2 into the form y=f(x) did not magically convert it to a function. So, y=sqrt(r^2 - x^2) is not a function -- but why? The concept of a 1:1 mapping was brought forward by my friend. So, I used the standard counter to that, namely that y=x^2 is indeed a function. Since values of y are repeated, why is that any different than having values of x repeated? Similarly, y=cos(x) is a periodic function in which values of y are repeated an infinite number of times...  So, what gives? My friend was right, but something critical was missing from the discussion.

You see, because we hadn't really discussed the concept of range, it was difficult to come up with a clear and indisputable response to the mapping problem. So, the discussion got tabled. But, the question still needed to be reconciled. The rigorous definition of a function goes something like this: for all x that are elements of the domain, there exists one (and only one) y that is an element of the range such that y=f(x). That is how the mapping works, but the definition looks like utter and complete rubbish in English. When I studied number theory and set theory many years ago, we would have used the following shorthand:

The rules for a function

This shorthand conveys everything in the English definition above rather succinctly. It also reveals a set of  truths upon further reflection:

• Each x can produce one (and only one) y
• The same value y can appear an infinite number of times, and that's totally okay.
• (Consider the expression y=3, and you'll get there quickly)
• A function doesn't have to make any continuous sense from the standpoint of a a single mathematical expression or formula.

The third bullet is not necessarily intuitive, but the following abomination is a graph of a proper function that meets all of the rules:

A rather odd-looking function

In this freaky function, the domain has been constrained to all Real Numbers between -x1 and +x2. For each value of x within this domain, one and only one value of y is produced by the function. The range would be defined as the set of all Real Numbers between some -y1 and +y2 which, respectively, represent the lower and upper values that the graph covers in the y axis. So, even though trying to build this ugly graph with a single mathematical expression is highly unlikely, it meets all of the criteria of a function.

In fact, I could have made it look worse.  There doesn't have to be any semblance of "continuity" in the mapping to the range! So, you could chop the x axis into several bits, and come up with different mathematical expressions for each bit, and the resulting whole could still be a function as long as it meets the rules.  Here's an example, with a domain defined as all Real Numbers from -300 to +300:

1. For x=-300 through x=-100, y = 7x^5 - 30x^3 + x - 40
2. For x>-100 but <0, y = tan(x^2)
3. For x=0 through x=10, y = -(3x^4) + 5
4. For x>10 but <100, y = (12.345x)/6.789
5. For x=100 through x=300, y=cosh(x)

That would be a convoluted graph, and I'm not going to pretend that I can draw it freehand in Photoshop with a mouse. But, the resultant insanity is indeed a valid function with a significantly huge range [(7 * ((-300)^5)) - (30 * ((-300)^3)) + (-300) - 40 = -1.700919 × 10^13], [cosh(300) = 9.71213198 × 10^129], and that [y=tan(x^2)] bit gets interesting all by itself (here's what it looks like from -100 to -99.9, and below is a wafer-thin slice that reaches the limits of what Google will plot!).

"...and that's all I have to say about that."