Reading: On the AdaCore LearnAda website click on the "Introduction to Ada" course on the left side of the page and start reading the sections on "Imperative Language" and "Subprograms." I also encourage you to read in my Ada tutorial, particularly sections 1.1, 1.2, and 1.4.
In this lab you will get some more practice writing Ada subprograms and using Ada control structures, etc. Along the way you might also learn some interesting math.
Using GitHub Desktop, go into your TutorialAda repository. Be sure you have no outstanding changes in whatever branch is selected. If you do, you should either commit them to your branch (but not master!) or, if they are unimportant, you can discard them (right-click on a changed file in GitHub Desktop and select "Discard changes"). Switch to the master branch, pull any updates, and create a branch for this lab. Recall that I do not recommend changing any files in the master branch.
Number theory is a branch of mathematics that concerns itself with the properties of the integers. One function of considerable interest in number theory is the prime counting function. It is traditionally given the name π (but it has nothing to do with circles). For example π(6) = 3 because there are three prime numbers less than or equal to 6 (namely, 2, 3, and 5).
Start by adding a function to package Number_Theory that computes π(n) for positive values n greater than or equal to 2. Note that the package already has a function Is_Prime that you will no doubt find useful. You might also want to make use of the defined subtype Prime_Argument_Type. Ada allows you to use Greek letters in variable names, but I suggest using the name Prime_Counting for π instead.
Modify the main file main.adb to exercise your function (ask the user to input a value n and then output π(n)). Here are some values of π(n) you can check.
| n | π(n) |
|---|---|
| 10 | 4 |
| 100 | 25 |
| 1_000 | 168 |
| 10_000 | 1_229 |
| 100_000 | 9_592 |
| 1_000_000 | 78_498 |
| 10_000_000 | 664_579 |
| 100_000_000 | 5_761_455 |
| 1_000_000_000 | 50_847_534 |
Computing π(n) exactly can be time-consuming, especially for large values of n (note: you should be able to double the speed of your implementation by skipping even numbers... don't forget to handle 2 as a special case). It turns out there is an approximation formula for computing π(n) that is much faster to calculate. It entails evaluating an infinite series that uses the natural logarithm function. Here is the series:
γ + ln(ln(n)) + ln1(n)/(1*1!) + ln2(n)/(2*2!) + ln3(n)/(3*3!) + ...
Here γ (gamma) is Euler's constant and has the value (approximately):
γ = 0.57721_56649_01532_86060_65120_90082_40243_10421_59335_93992
Although the series has infinitely many terms you don't need to add them all because the terms get smaller and smaller. This series is called the "logarithmic integral function" and goes by the name li(n). It is an amazing fact that π(n) is roughly equal to li(n).
Add a function to your package Number_Theory that computes li(n). Call your function Logarithmic_Integral.
The package Ada.Numerics.Generic_Elementary_Functions contains a function Log which computes the natural logarithm (shown as 'ln' in the formula above). Note that the logarithmic integral is computed using floating point numbers, so you'll need some type conversions to go back and forth between integers and floating point values. For example if N is an integer of some kind, you can convert its value to the floating point type declared in Number_Theory by doing Floating_Type(N).
Modify your main program to print out both the exact value of π(n) and your computed value of li(n) to compare them. To do this you will need to instantiate the Ada library package Float_IO for your specific floating point type.
package Floating_IO is new Ada.Float_IO(Number_Theory.Floating_Type);
After doing this, you will have access to a procedure Floating_IO.Put that knows how to print the floating point type used by package Number_Theory.
It turns out that π(n) < li(n) for all the values of n we are interested in using. Add a postcondition to your Logarithmic_Integral function that states this. This postcondition is a partial statement of correctness. If the postcondition is violated something is definitely wrong. However, your Logarithmic_Integral function could still be wrong and satisfy the postcondition anyway.
Actually π(n) < li(n) is not always true. For very large values of n it becomes false. Exactly where that happens is not precisely known, but the values required are huge. See this fascinating Wikipedia article for more information.
For this lab, zip together your modified specification and body of package Number_Theory, and your modified main, and submit the zip archive to Canvas. It would be helpful to me if you named the zip file using the first letter of your first name followed by your last name. For example: pchapin.zip (except use your own name). This is not an absolute requirement, but it makes things a little quicker for me.
Last Revised: 2022-02-01
© Copyright 2022 by Peter C. Chapin <pchapin@vtc.edu>