Tuesday, August 31, 2010

Project Euler and OCaml prime number list generator

Half a year has passed... The main reason why I didn't write anything concerning Ruby golfing is mainly because I stopped practicing quite a while ago, so I do not have any fresh tips to write about now.

Recently, I am mostly spending my time learning the programming languages Clojure and Factor, using them to solve Project Euler problems. Clojure reminds of Scheme, but I am very new to the concatenative paradigm of Factor, as I never learned Forth or any similar language.
Providing a fairly succinct syntax, they perform very well, which is the main reason why I'm now using them over Ruby.

Some weeks ago, this article in which are analyzed the results of the programming language benchmarks game made me want to use again the OCaml language, that I had previously learned and used during my studies at the university. This analysis shows it as an almost ideal programming language in terms of code size vs performance trade-off.

Several problems of the Project Euler deal with prime numbers, so I needed some code to generate them. Unfortunately, I couldn't find any simple prime generating code on the internet: it seems that finding OCaml code snippets is not an easy task...
Here is quite simple implementation of the Sieve of Eratosthenes which is quite fast (even when running only bytecode) and should be enough for most of the problems that require to use prime numbers in the int range:

Which will for example produce the fo! llowing result:
# let primes = primes_upto 4000000 i!  n
List.nth primes ((List.length primes) - 1);;
- : int = 3999971

For problems requiring bigger primes, but not an exhaustive list of them, using algorithms such as the Miller-Rabin primality test is a better choice.

List prime numbers

Graphing Linear Functions

Just recently I was working with a student on graphing Linear Functions during a tutoring session. She asked if there was anything she could work on to continue with her practice. This prompted me to get on the computer and do a search for some lessons and interactives that might help her.

I started my search with Hippocampus.org. The full Algebra 1 class has an entire chapter devoted to graphing Linear Functions. This is a wonderful place for students to start if they are having trouble with the concept or need a refresher.

I also came across some great interactives that can really help students. The first is an online graphing utility that I have used in the past called GCalc. This will allow student! s the ability to graph any function, including Linear Functions.

The second is a Shodor Interactive that will also allow students to graph Linear Functions. You may ask why give students an opportunity to graph functions with technology instead of with paper and pencil methods. I am a huge proponent of doing both. Students need to know the mechanics of graphing functions on their own, but we should also expose students to the technology that is available to them.

I also found two sliding interactives. Students are able to move a slide that changes the slope and y-intercept of an equation and they can see how these changes affect the graph of a linear function. One of these interactives can be found at mathsnet and the oth! er at id.mind.

Finally, I found a site that offers free graph paper. I think that is also important when students are practicing these skills.

Linear Functions

GAMS: Piecewise linear functions with SOS2 variables

Sometimes we need to represent a piecewise linear function, like:

sos2-1

This can be modeled with the following:

sos2-2

Equation (1) is ! called the “reference row”, equation (2) the “function row” and equation (3) the “convexity row”. Many MIP solvers have so-called SOS2 facilities: special ordered sets of type 2. The lambda variables form a SOS2 set, so this makes using this very simple (it is possibly to simulate this with extra binary variables). In GAMS this looks like:

variables y,x;
sos2 variables lambda(k);

equations refrow, funrow, convexity;

refrow.. x =e= sum(k, lambda(k)*xbar(k));
funrow.. y =e= sum(k, lambda(k)*ybar(k));
convexity.. sum(k, lambda(k)) =e= 1;

Notes:

  • It is important to keep the “set-index” last. See the fragment of a model I am working at now:

defq(i,t).. q(i,t) =e= sum(ic(i,c)! , lambda(i,t,c)*xpoints(c));

d efcost(i,t)..  cost(i,t) =e= sum(ic(i,c), lambda(i,t,c)*ypoints(i,c));

convex(i,t)..  sum(ic(i,c),lambda(i,t,c)) =e= 1;

Here we need to keep c last in variable lambda. This makes sure we have i × t sets with c members. In this case c is dependent on i through the set ic(i,c).

  • AMPL has special language constructs to make this even easier.
  • MS Solver Foundation also has added SOS2 support.
  • GAMS has no facility to specify the reference weights (they are usually automatically generated to be 1,2,…).  Of course in many cases I can not make a good use of reference weights anyway, as I would not know any better values.

Linear Functions

Dynamical Systems - 8/4/10

Today, we were treated to a quick introduction to dynamical systems, an area of math which focuses on repeated iteration of maps to study long-term or asymptotic behavior associated with this iteration.

We started by taking a simple example. Consider a real valued function f from R to R. Then consider the sequence of points (x, f(x), f(f(x)) ....) We call this sequence the orbit of the point x.

Let us take f(x) = kx(1-x), which is the equation for a quadratic function. Also consider the identity map, g(x) = x.
For now, we take k >0.
Depending on our specific value of k, we have a parabola which intersects the g(x) either once or twice.

We are interested in the fixed points of f. As the name implies, these are points where the map f leaves a point in its domain fixed, or in symbols: f(x1) = x1.
We wish to study asymptotic behavior of functions. To do this, we! pick a point x on the real line and first apply the function. This gives us a new point f(x). Then we find f(f(x)). Since we have the identity map also drawn in (in this case, g(x)), this process is applying f, moving horizontally to g, moving vertically to f, and so on.

We see that repeating this process, we notice two general patterns: In some situations, we may continue onward towards positive or negative infinity in an unbounded fashion. However, for other sections of the real line, we see that there is a convergence towards certain fixed points.

We call a fixed point x attracting if the magnitude of its derivative at x is less than 1 and we say a fixed point is repelling if the magnitude of its derivative at x is greater than 1.

We see then that the derivative of the function at these fixed points greatly affects this convergence behavior.

Afterwa! rds, we moved on to dynamics of complex functions which map th! e comple x plane to itself.

We first took f: C -> C (complex plane to itself) given by f(z) = z^2 + c for some complex number c.

If we let c = 0, then points inside the unit disk spiral towards the origin. Points outside the unit disk spiral to infinity. We see that points on the unit circle itself get mapped to other points on the unit circle (their length is preserved, but they rotate.) Thus the mapping leaves the unit circle invariant. Furthermore, we see that iterates of the map can map a small section of the unit disk onto the whole unit disk.

We now consider the effect of varying our complex number c. For c very small, we obtain a similar picture: the interior of the curve spirals inward to the center, the curve itself is invariant, and the outer regions escape to infinity.
For very large x, most points escape outward to infinity.

We then construct the Mande! lbrot set as the set of points c such that the n-th iterate of the map f does not go to infinity when evaluated at the point c itself for technical reasons.
We take all parameters c and iterate at the point c itself.

Similar to our notion of fixed points, we say a point z in the complex plane is periodic with a period n if the n-th iterate of f applied at z = z.

We concluded by seeing various pictures of the Mandelbrot set and fractals constructed through similar dynamical systems in the complex plane.




Solve for Angle of Intersection between Curves

Percent of change

When some quantity changes, such as a price or the amount of students, we can measure either the absolute change ("The price increased by $5" or "There were 93 less students this year"), or the percent change.

In percent change, we express WHAT PART of the original quantity the change was.

For example, if a gadget costs $44 and the price is increased by $5, we measure the percent change by first considering WHAT PART $5 is of $44. Of course the answer is easy: it is 5/44 or five forty-fourths parts.

To make it percent change, however, we need to express that part using hundredths and not 44th parts. this happens to be easy, too. As seen in my previous post, you COULD make a proportion to find out how many hundredths 5/44 is:

5/44 = x/100

To solve this, you simply go 5/44 x 100, which is easy enough to remember in itself. In fact, this is the rule often given: you compare the PART to the WHOLE using division (5/44),! and multiply that by 100.




There were 568 students one year, and 480 the next year. By how may percent did the student population decrease?

You first calculate the absolute change, which is 568 − 480 = 88. Then we find what part of the original population is 88 (it is 88/568), and express that using hundredth parts (percents):

88/568 x 100 = 15.49%

The student population decreased by 15.49%.




Often we are given the opposite problem: we know the percent of change and the original situation, and are asked about the new situation.

The price was $4.55 and increased by 14.78%. What is the new price?

Here, we'd need to find the price increase, or the absolute change in price first. We know the percent part of the total (it is 14.78/100) and the total amount, so multiplying those we get the part as a dollar-amount: 14.78/100 x $4! .55 = $0.67249. So this is the increase. To find the new price! , add th e increase to the original: $4.55 + $0.67249 = $5.22249 = $5.22.

Instead of multiplying by 14.78/100, it is far quicker to multiply by 0.1478 — or to change the percent-amount 14.78% to a decimal 0.1478 and multiply by it.

And, since in the end we need to add the original total, the whole calculation looks like this:

0.1478 × $4.55 + $4.55

Here, using distributive property we can make it look like this:

= $4.55 (0.1478 + 1) = $4.55(1.1478) = 1.1478 × $4.55

So it can all be done in one multiplication. Instead of multiplying by the decimal 0.1478, you add 1 to it before multiplying.




Then one more possible problem type is that you know the percent of change and the actual change amount (absolute change), and are asked the original and/or the new total.

The price increased by 13%, or by $10.14. What was the original price?

! Let the original price be p. Then you can build an equation based on the idea that the price increase is 13% of p:

0.13p = $10.14   or   13/100p = $10.14

p = $10.14/0.13 = $78.

The new price would be found by adding.




Some other lessons to read are below:

Percent Of Change - Lesson and Problems

General Increase and Decrease Examples from Purplemath.com

Percent of change calculator - enter the original and the changed quantities, and it calculates the percent of change.

PERCENT INCREASE OR DECREASE lesson from TheMathPage.com


Find percentage

Unneccesary Medical Tests: Tort Reform Can't Solve it All

Gastroenterologist's view of the stomach

Recently, while covering for one of my partners on a weekend, I was consulted by a physician to do a procedure. The doctor wanted his patient to undergo an EGD, which is a scope test that examines the esophagus, stomach and first portion of the small intestine called the duodenum. We gastroenterologists do this test routinely to search for an explanation for a patient’s symptoms, or to determine if these organs might be harboring a lesion that is silently bleeding.

Gastroenterologists are obligated to perform procedures for sound medical reasons. I have already confessed publicly on this blog why physicians like me have performed medical tests for the wrong reasons. The medical universe is not ideal, and neither are its players. Nevertheless, we want our care to make sense and not to waste dollars. For example, if a patient is suffering an acute headache, it would be hard to justify ordering a CAT scan of the abdomen, which would be unlikely to explain the symptom. One reason that wrong tests are done is because physicians ask colleagues for a specific procedure, and not for their cognitive advice.

For example, when we order a radiology examination, such as routine x-rays, CAT scans, MRIs, etc., we are not requesting the radiologist’s opinion on the medical issue, only that the test be performed. For ordinary readers who are on the sidelines of the medical arena, here’s how it works.

• A doctor like me decides that a patient needs a CAT scan.
• I order it.
• The radiologist does it.

Personally, I think this is a serious failing in medical practice. Radiologists have the deepest expertise in the procedures they do, yet they are not routinely consulted in advance. If they had knowledge of the particular patient, they could advise us if our intended test is the best option. Perhaps, a different radiology test would clarify the clinical issue better. Or, perhaps, we ordered the proper test, but it should be performed using special technique. In general, radiologists are not treated as true consultants, but as technicians. By doing so, clinicians like me who take care of patients are squandering an opportunity to practice better medicine. 

Of course, there are many times that physicians and radiologists do confer to optimize the diagnostic approach. But, in my experience, these important conversations are exceptional. Physicians who order imaging studies on their patients likely feel that they have enough knowledge to choose the right exam. Some do, and some don’t.

I have never liked serving as a technician gastroenterologist, but I am often asked to do so. Like every other gastroenterologist, I have performed requested procedures that were reasonable, but that I would not have personally recommended if my advice had been sought. The patient referenced at the top of this post was in a different category. This was not a 'gray area' issue.

This particular patient was having some minor rectal bleeding. He had already had the pleasure of a full colonoscopy this past November, when hemorrhoids were discovered. No additional testing was necessary for the current minor bleeding, as hemorrhoids were the likely culprit. The request for an EGD was nonsensical. The ordering physician had no economic conflict of interest in ordering the test; only the gastroenterologist would benefit financially. An EGD here was like ordering a foot x-ray on a patient with a sore throat.

I will now risk outrage from my medical colleagues by sharing a dark secret with the public. I will divulge two pieces of confidential medical code, and trust you all to protect me from vengeful physicians who will accuse me of breaking sacred medical omerta. In other words, what you read on Whistleblower, must remain here.

At the very bottom of my consultation report, I wrote: ‘will discuss with you’. This is standard medical code for, your request is nuts and I won’t put in writing what I really think. When a doctor uses this phrase, it means that a private conversation between the consulting and referring physician will soon follow. Ask your own doctor what the phrase ‘will discuss with you’ means, but be prepared for garbled gobbledygook seasoned with a dash of doublespeak.

Later that day, my partner continued the discussion with the physician and gently asked for his rationale for requesting the EGD. Here comes secret code #2. The referring physician wanted the EGD 'for completeness’. When a doctor uses this phrase, as we all have done, it means, the test makes no sense and is totally unnecessary.

So, what happened? Monday morning, the gastroenterologist who was originally consulted assumed care of the case. The EGD was done.

Fear of litigation results in overutilization of medical care. I know this personally. But, there are other reasons why we physicians pull the procedure trigger. This vignette illustrates that our profession has its own healing to do.  Tort reform can't cure it all.

While I didn’t perform the EGD, am I an accomplice by not standing up to the referring physician initially?  Can I rightfully still consider myself to be an ethical practitioner?  Radiologists don’t refuse to do CAT scans that make no clinical sense. Should the standard be different for other medical procedures, which have very low risks of complications? What would you have done here? Would you have refused the physician's request, which would likely result in the loss of this physician’s future referrals? Would you rationalize the unnecessary test knowing that if you didn’t do the EGD, that someone else would? Do private pracitioners view this scenario differently than employed physicians? Should they?

Do you have similar vignettes from your own practice or experience that you can share?

Solve equivalent fractions and get practice

What Are These Good For?

Really. I want to know.


Arc Length Of Circle Theorems