Today I was trying to calculate e.
I find that when I try to calculate things that involve either large exponents or sums of large series regular calculators just don't seem to cut it.
Today's calculation was for e using the formula given with limit notation:
e = lim x -> infinity (1+1/x)x
To do this I decided to select a value of x that is large enough to give a reasonable approximation for the first few digits... 25000
I don't know about you, but I havn't found many hand calculators that like to do things like raise numbers to high powers. Most graphing calculators can, but I don't always have one of those around.
The other thing I really appreciate is being able to work with rational numbers without introducing rounding error with floating point.
If I divide 3 by 4 in most calcualtors I would get .25. In lisp I get a fractional number of 3/4. In instances where you really care about rounding error this is a great feature.
The only down side is the calculation time. While I know I'm getting a good number, it can take a little longer. I have generated numbers multiple screens long. When you're dealing with these large numbers without loss you can get into trouble where you are maintaining accuracy you don't need.
For instance, in cryptography when you are trying to find C=PE (mod n) you can apply mod n to each step of finding PE. This keeps the number small enough to be operated upon.
Lisp may not be the best calculator around, but it sure helps get the job done when you need to operate on rational numbers.
Sunday, February 04, 2007
Saturday, February 03, 2007
Getting back into things. (Plus a rant)
I haven't been blogging in almost a month. Really, I would have liked to, but how exactly blog about looking for work when you would be leaving multiple jobs at the same time?
Well, backcountry.com ended up offering me a job. It's great, I'm surrounded by smart people. Plus, it's a jump in pay. My main job that I just left was bought last month. You can read sarahbellum's recent thoughts on the matter. Suffice it to say, being a programmer and otherwise curious guy there wasn't much point to me sticking around to do sysadmin, helpdesk, or anything that involves user support.
You might say I've gone to a better place...
For what it's worth, I don't plan on working anywhere that is subject to FDA regulations ever again. It's not that I have any problem with laws that are meant to make people safe.
(I do have some problems with laws that make us more "safe", but that's no my FDA problem.)
No, being a citizen of this fine country I have taken it upon myself to be educated as to its operation. For those of you who may not be from around here, or who never took a civics class here's the breakdown of how laws are made (simplified):
The congress passes bills by voting on them.
The president signs bills into law and manages the departments that do enforcement.
The judicial branch looks at those laws and provides a process for making sure that the laws and their enforcement are within the scope of authority of what the congress and president can do.
Now this system works pretty well. If there is a rule that anyone is bound by there has to have been some unit of government (city, county, state, etc...) that has undergone the due process to make it follow this pattern.
The legislative makes the laws.
The executive enforces the laws.
The judicial determines if the laws are correct/valid.
Well, here we have the FDA. It was created by an act of congress, signed into law by the president, and allowed to continue by the judicial. Everyone dropped the ball.
Why is this a problem?
The congress has the authority to make laws by way of simple majority with the president's signature, or with a 2/3 majority overriding the president.
The congress was not granted authority to delegate its law making authority.
The FDA has a rule making process. The people who make the rules have been placed there by congress, but they are not subject to reelection as are the members of congress. These rules are enforced with the same effectiveness as other laws, but in the case of infractions you are subject to other FDA rules or laws that have been passed by the congress. It's kind of messy.
The biggest problem with this is that if you break an FDA regulation the only remedy is to work with the FDA. There is not a judicial due process in place.
That is to say, when a regulation is broken there is not a judicial line of authority (appeal process) that leads to the supreme court. This precludes regulations from being judged as to their constitutionality.
For what it's worth, I really like our form of government. It would work really great if we used it the way it was designed.
Before we can really be free enough to have a real constitutional government people have to respect the boundaries that are so important to keeping it going. Even worse is that the current iteration we are living under now will have to collapse under its own corruption before it can be replaced by good people who will not support such corruption.
Is my dearest hope that I may one day be worthy to live among people who can abide by a constitutional form of government the way it was meant to be used.
Well, backcountry.com ended up offering me a job. It's great, I'm surrounded by smart people. Plus, it's a jump in pay. My main job that I just left was bought last month. You can read sarahbellum's recent thoughts on the matter. Suffice it to say, being a programmer and otherwise curious guy there wasn't much point to me sticking around to do sysadmin, helpdesk, or anything that involves user support.
You might say I've gone to a better place...
For what it's worth, I don't plan on working anywhere that is subject to FDA regulations ever again. It's not that I have any problem with laws that are meant to make people safe.
(I do have some problems with laws that make us more "safe", but that's no my FDA problem.)
No, being a citizen of this fine country I have taken it upon myself to be educated as to its operation. For those of you who may not be from around here, or who never took a civics class here's the breakdown of how laws are made (simplified):
The congress passes bills by voting on them.
The president signs bills into law and manages the departments that do enforcement.
The judicial branch looks at those laws and provides a process for making sure that the laws and their enforcement are within the scope of authority of what the congress and president can do.
Now this system works pretty well. If there is a rule that anyone is bound by there has to have been some unit of government (city, county, state, etc...) that has undergone the due process to make it follow this pattern.
The legislative makes the laws.
The executive enforces the laws.
The judicial determines if the laws are correct/valid.
Well, here we have the FDA. It was created by an act of congress, signed into law by the president, and allowed to continue by the judicial. Everyone dropped the ball.
Why is this a problem?
The congress has the authority to make laws by way of simple majority with the president's signature, or with a 2/3 majority overriding the president.
The congress was not granted authority to delegate its law making authority.
The FDA has a rule making process. The people who make the rules have been placed there by congress, but they are not subject to reelection as are the members of congress. These rules are enforced with the same effectiveness as other laws, but in the case of infractions you are subject to other FDA rules or laws that have been passed by the congress. It's kind of messy.
The biggest problem with this is that if you break an FDA regulation the only remedy is to work with the FDA. There is not a judicial due process in place.
That is to say, when a regulation is broken there is not a judicial line of authority (appeal process) that leads to the supreme court. This precludes regulations from being judged as to their constitutionality.
For what it's worth, I really like our form of government. It would work really great if we used it the way it was designed.
Before we can really be free enough to have a real constitutional government people have to respect the boundaries that are so important to keeping it going. Even worse is that the current iteration we are living under now will have to collapse under its own corruption before it can be replaced by good people who will not support such corruption.
Is my dearest hope that I may one day be worthy to live among people who can abide by a constitutional form of government the way it was meant to be used.
Friday, January 05, 2007
I finally get RSA
Over the last week or so I've been trying to figure out how RSA encryption works. I've been reading books like In Code, and Number Theory.
Today I can say that I properly understand how to do RSA style encryption.
It all starts with finally understanding congruences...
C ≡ PE(mod n)
and
P ≡ CD(mod n)
where P = plain text and C = Cipher text
For the readers at home this is read as:
C is congruent to P raised to the E power modulo n
This means that if you divide C by n, or P raised to the E by n you will get the same remainder. In the case of cryptography you are seeking C which IS the remainder.
To make life easier I'll write it in a more friendly programming notation:
C = (P^E)%n
Once I understood this much the next part was figuring out how to come up with valid values of n, E, and D. What follows is how you come up with an RSA key.
Before we can find n we need to mind our p's and q's.
p and q are primes.
For the sake of this exercise we will select 31 and 17 as our primes.
p = 31
q = 17
n = p * q = 527
φ(n) = (p-1) * (q-1) = 480
The last one: φ(n) gives us the modulous we need as a base for finding D and E.
We need to find a number that is relatively prime to φ(n) (no common factors). We can use the euclidian algorithm to determine the greatest common divisor. I'll post code at the end.
Let's try 41 for E.
gcd(480,41) = 1
E=41
Now we need to find D, the multiplicative inverse of E modulo φ(n).
41*D ≡ 1(mod 480)
This part took me 3 days to figure out. It finally came together when I read about the Extended Euclidean algorithm on wikipedia. I wrote a function that returns the multiplicative inverse based on the modulous.
In this case D = 281.
We have generated a bunch of numbers:
p = 31
q = 17
n = 527
φ(n) = 480
E = 41
D = 281
Now we need to discard p, q, and φ(n).
In RSA encryption p and q are large prime numbers (100+ digits). The reason why it is secure is you need to know p and q to get D from E. When n is the product of large primes it becomes very time consuming to factor back to those primes.
Finally, this leaves us with our key pair.
KE = (41,527)
KD = (281,527)
Now for the code of the gcd function and the multiplicative inverse modulo base function:
(Forgive the indentation, I know no good way of doing this with blogger)
(defun eu-gcd (base num)
(let ((remainder (mod base num)))
(if (eq remainder 0)
num
(eu-gcd num remainder))))
(defun inverse-modulo (base num &optional (b1 0) (b2 1) orig-base)
(let* ((di (mod base num))
(k (- 0 (/ (- di base) num)))
(bi (- b1 (* k b2))))
(if (eq di 1)
(mod bi orig-base)
(inverse-modulo num di b2 bi (if orig-base orig-base base)))))
Today I can say that I properly understand how to do RSA style encryption.
It all starts with finally understanding congruences...
C ≡ PE(mod n)
and
P ≡ CD(mod n)
where P = plain text and C = Cipher text
For the readers at home this is read as:
C is congruent to P raised to the E power modulo n
This means that if you divide C by n, or P raised to the E by n you will get the same remainder. In the case of cryptography you are seeking C which IS the remainder.
To make life easier I'll write it in a more friendly programming notation:
C = (P^E)%n
Once I understood this much the next part was figuring out how to come up with valid values of n, E, and D. What follows is how you come up with an RSA key.
Before we can find n we need to mind our p's and q's.
p and q are primes.
For the sake of this exercise we will select 31 and 17 as our primes.
p = 31
q = 17
n = p * q = 527
φ(n) = (p-1) * (q-1) = 480
The last one: φ(n) gives us the modulous we need as a base for finding D and E.
We need to find a number that is relatively prime to φ(n) (no common factors). We can use the euclidian algorithm to determine the greatest common divisor. I'll post code at the end.
Let's try 41 for E.
gcd(480,41) = 1
E=41
Now we need to find D, the multiplicative inverse of E modulo φ(n).
41*D ≡ 1(mod 480)
This part took me 3 days to figure out. It finally came together when I read about the Extended Euclidean algorithm on wikipedia. I wrote a function that returns the multiplicative inverse based on the modulous.
In this case D = 281.
We have generated a bunch of numbers:
p = 31
q = 17
n = 527
φ(n) = 480
E = 41
D = 281
Now we need to discard p, q, and φ(n).
In RSA encryption p and q are large prime numbers (100+ digits). The reason why it is secure is you need to know p and q to get D from E. When n is the product of large primes it becomes very time consuming to factor back to those primes.
Finally, this leaves us with our key pair.
KE = (41,527)
KD = (281,527)
Now for the code of the gcd function and the multiplicative inverse modulo base function:
(Forgive the indentation, I know no good way of doing this with blogger)
(defun eu-gcd (base num)
(let ((remainder (mod base num)))
(if (eq remainder 0)
num
(eu-gcd num remainder))))
(defun inverse-modulo (base num &optional (b1 0) (b2 1) orig-base)
(let* ((di (mod base num))
(k (- 0 (/ (- di base) num)))
(bi (- b1 (* k b2))))
(if (eq di 1)
(mod bi orig-base)
(inverse-modulo num di b2 bi (if orig-base orig-base base)))))
How political thinking in utah works
This morning I was thinking about it and realized that my car was hit right under my Pete Ashdown sticker.
I began channeling the standard utah-party-politics-religion paranoia and was thus led to the conclusion that an Orrin Hatch supporter was subliminally led to drive poorly in the Dan's parking lot!
That's it! Republicans don't think democrats should drive decent looking cars!
I'll show them. I'll support legislation that bans business owners from writing off those nice cars they lease. We all know that ALL republicans are business owners so I'll be able to stop them from having nice cars too!
The only trouble is that it won't stop there...
Next week when I get an oil change I'm going to have to make sure that it's a good democrat that does it. If I let a republican do it who knows what they'll sabotage on my car!
You see, those republican business owners want me to do my part in saving the economy by buying things I don't need. Like say, a new car.
The really devious part of it all is that you know the major car companies are run by republicans. That's the real reason they want me to buy a new car. It's all about selling their wares!
Retarded isn't it?
You can't have a reasonable discussion if you're competing with thinking that is on this level. If you don't believe me just wander around the conventions of both political parties and listen in on a few conversations.
If you're not with us you're a heretic.
Who suffers from this? The citizens.
Can you participate in the parties without getting sucked into it? Not really.
I began channeling the standard utah-party-politics-religion paranoia and was thus led to the conclusion that an Orrin Hatch supporter was subliminally led to drive poorly in the Dan's parking lot!
That's it! Republicans don't think democrats should drive decent looking cars!
I'll show them. I'll support legislation that bans business owners from writing off those nice cars they lease. We all know that ALL republicans are business owners so I'll be able to stop them from having nice cars too!
The only trouble is that it won't stop there...
Next week when I get an oil change I'm going to have to make sure that it's a good democrat that does it. If I let a republican do it who knows what they'll sabotage on my car!
You see, those republican business owners want me to do my part in saving the economy by buying things I don't need. Like say, a new car.
The really devious part of it all is that you know the major car companies are run by republicans. That's the real reason they want me to buy a new car. It's all about selling their wares!
Retarded isn't it?
You can't have a reasonable discussion if you're competing with thinking that is on this level. If you don't believe me just wander around the conventions of both political parties and listen in on a few conversations.
If you're not with us you're a heretic.
Who suffers from this? The citizens.
Can you participate in the parties without getting sucked into it? Not really.
Thursday, January 04, 2007
The wonders of Costco
Tonight I called Andy and we went to costco for dinner. It was a pretty ordinary trip. I picked up some bacon and some other food. We paid and decided to get some pizza.
While we were eating, a couple of employees were taking apart some tables. Andy and I overheard how they were trying to figure out how to throw them away.
I knew I had to act fast.
I inquired whether or not I could take one if they were throwing them away. They asked their supervisor and I got myself one free table.
I'm going to have to say that this is the coolest free table I've ever gotten.
While we were eating, a couple of employees were taking apart some tables. Andy and I overheard how they were trying to figure out how to throw them away.
I knew I had to act fast.
I inquired whether or not I could take one if they were throwing them away. They asked their supervisor and I got myself one free table.
I'm going to have to say that this is the coolest free table I've ever gotten.
Hit & Run
As far as I'm concerned there are only two types of hit & run.
There's the fun type:
And the not fun type:
Some call me a crazy driver, but to my credit I have yet to damage someone elses car while driving.
There's the fun type:
And the not fun type:
Some call me a crazy driver, but to my credit I have yet to damage someone elses car while driving.
Tuesday, January 02, 2007
Huzzah! for no clichés
I was going through my RSS reader and found this blog post on coding horror: On the Use of Clichés.
I cut the text of my last post and pasted it into the cliché finder that was referenced. I felt special when it found nothing.
Now to keep up the not quite bad writing...
I cut the text of my last post and pasted it into the cliché finder that was referenced. I felt special when it found nothing.
Now to keep up the not quite bad writing...
Subscribe to:
Posts (Atom)
