News for hackers. Stuff that matters.
Re:My Favorite Programming Problem to Teach: Digit Length by userbinator on Sunday November 10, 2019 @10:43PM (#21501955)
Strings are disallowed because they are not necessary for this problem and although the solution is shorter, is far more inefficient; it also doesn't demonstrate the algorithmic thinking that the course is obviously trying to teach.

I've taught CS courses before, and have seen plenty of self-proclaimed self-taught know-it-alls who seem to be more stackoverflow-copy-pasters than anything else.

Re:My Favorite Programming Problem to Teach: Digit Length by rmetzler on Monday November 11, 2019 @01:00AM (#21502525)
There are other HN comments pointing out that the proposed solution still doesn't work correctly because of floating point operations. If the goal is to learn something about programming, yes, I agree with you. But if the goal is to write code with as few bugs as possible then I would take the "create a string and count chars" solution over every solution involving floating point math.
Re:My Favorite Programming Problem to Teach: Digit Length by svnpenn on Sunday November 10, 2019 @10:48PM (#21501977)
> Strings are disallowed because they are not necessary for this problem

the division examples are not necessary either, thats the point. you can solve it different ways, that doesnt mean one way is not necessary, it just means its different. one may be faster, one may be more readable. If you dont allow different solutions you cant explore the tradeoffs between them.

Re:My Favorite Programming Problem to Teach: Digit Length by tzs on Monday November 11, 2019 @11:58AM (#21506394)
Generally, the purposes of the exercises in a class is to reinforce the material that has been taught up to that point and to demonstrate that the student can use it.

For example, if early in an elementary number theory class the student is asked to prove that there are in infinite number of primes of the form 4n+3, a solution that just invokes Dirichlet's theorem on primes in arithmetic progressions would probably not be acceptable. That approach does work to show that there are an infinite number of 4n+3 primes, but completely fails to show that that the student understood the material actually taught in class.

It's the exact same thing with the digit counting problem. Solving it by just invoking the built in string length function does little to demonstrate that the student understands the material taught so far.

Re:My Favorite Programming Problem to Teach: Digit Length by jstrieb on Monday November 11, 2019 @10:06AM (#21505371)
I note that the solution is invalid at the bottom of my post, but it is worth mentioning that I know all of the students in the group session when I teach this problem, and I am familiar with their background. If I know that a student has prior Python experience, I will discuss the string solution with them, but let them know not to use it in their homework until strings have been covered in class.

In this case, even though the solution is disallowed for grading purposes, there is an opportunity to discuss it during the lesson.

Re:My Favorite Programming Problem to Teach: Digit Length by pd0wm on Monday November 11, 2019 @03:26AM (#21503042)
Funny fact: the python round implementation actually uses strings. https://github.com/python/cpython/blob/master/Objects/floato...
Re:My Favorite Programming Problem to Teach: Digit Length by saagarjha on Monday November 11, 2019 @12:02AM (#21502274)
> is far more inefficient

Is it?

Re:My Favorite Programming Problem to Teach: Digit Length by bjoli on Monday November 11, 2019 @01:33AM (#21502682)
Probably not, at least not compared to the naive solution using Euclidean division.

for larger numbers it is probably faster.

Re:My Favorite Programming Problem to Teach: Digit Length by hoseja on Monday November 11, 2019 @04:17AM (#21503242)
It's Python. Efficiency has gone out the window long ago.
Re:My Favorite Programming Problem to Teach: Digit Length by hinkley on Monday November 11, 2019 @12:12AM (#21502323)
Why do you need to know the decimal length of a number if not for display purposes? If you have one then make that the problem.

I wonder what would happen if you implemented itoa and then counted digits. It’s pretty much the same thing.

Re:My Favorite Programming Problem to Teach: Digit Length by throwaway744678 on Monday November 11, 2019 @02:20AM (#21502844)
We're lacking a bit of context here, but this is a good way of understanding the relationship between number of digits, closest power of ten, math.log and decimal representation. Once you understand it, it works the same in any base; in particular in base 2. This would be a necessary step should you want to implement some data structures (eg. quadtrees, octrees, etc. which heavily rely on powers of two). You wouldn't expect the implementation to measure the length of the binary string representation!

Regarding itoa(), the first implementation provided in the article actually match it's implementation, without the unnecessary bits (building the output).

Re:My Favorite Programming Problem to Teach: Digit Length by slavik81 on Monday November 11, 2019 @05:15AM (#21503528)
I wish they didn't phrase it as being about removing a loop. If math.log10 supported arbitrary integer inputs, there would be a loop inside.

They should consider the upper bound of their algorithm. Because it uses floating point, it doesn't work for all natural numbers, as required by their specification.

To address your point, counting digits in base 2 is much simpler than in base 10, because the internal representation of the number on the computer is already base 2. You can use numeric calculations, but you can also just look at your digits.

(Edited for fewer tangents and to be more positive.)

Re:My Favorite Programming Problem to Teach: Digit Length by gpderetta on Monday November 11, 2019 @09:42AM (#21505170)
Once you compute your log2, computing log10 is just a single multiplication though, so, it is in fact as most as easy.
Re:My Favorite Programming Problem to Teach: Digit Length by MauranKilom on Monday November 11, 2019 @10:56AM (#21505807)
It's a single multiplication - with an irrational (transcendental, actually) number. That is most certainly not "easy" for a computer, and elsewhere in the comments you can see how much of a problem that actually poses.

Also, counting digits in base 2 is not the log2. The former gives you the latter but not the reverse. Finding the number of decimal digits in a number given in base 2 is not a simplification.

Re:My Favorite Programming Problem to Teach: Digit Length by gpderetta on Monday November 11, 2019 @11:50AM (#21506329)
Oh, agree that for arbitrary large or non integer inputs it might not work. But elsethread jepler has shown a solution off Hacker's Delight which which simply multiplies the index of the most significant bit with a magic constant.
Re:My Favorite Programming Problem to Teach: Digit Length by MauranKilom on Monday November 11, 2019 @02:32PM (#21508050)
> But elsethread jepler has shown a solution off Hacker's Delight which which simply multiplies the index of the most significant bit with a magic constant.

...and then checks for and corrects the potential off-by-one thus incurred.

Re:My Favorite Programming Problem to Teach: Digit Length by slavik81 on Monday November 11, 2019 @02:46PM (#21508174)
When N is fixed, all algorithms become O(1). That's why they appear the same.

If you do these calculations by hand, the complexity will be more obvious because each operation will be smaller.