Solving simple problem correctly the first time (C++ Learning Community)

Title: Solving simple problem correctly the first time
Description: A challenge

KTC - September 6, 2005 07:13 AM (GMT)

This is lifted straight out of an article in CUJ, but I thought it might be a interesting challenge for people here.

Who would be prepare to try their hands at writing a (small) program that they are confident will work correctly the first time? No testing, no debugging.

The problem:
How many decimal digits are in a given unsigned integer?

QUOTE

For the purpose of this problem, we are not allowed to use any library functions — particularly library functions that convert integers to strings — because then we would be using someone else's solution to the problem instead of solving it ourselves. Moreover, we must not use any floating-point arithmetic, because of the intrinsic difficulty in understanding the rounding problems that might come up."

The problem (slightly more difficult):
Same as above, but does not involve recursion.

The problem (more difficult):
Same as aboves, but with signed integers.

p.s. I'll post a link to the article later, when people have had a try at it.

C-Man - September 6, 2005 09:14 AM (GMT)

CODE

#include <stdio.h>

int digits (int i)
{
int n = 0;
do {
++n;
}
while (i /= 10);
return n;
}

int main ()
{
int i;
puts ("Input a number :");
scanf ("%d",&i);
printf ("It's a %d-digit number\n",digits (i));
}

don't blame me if it doesn't compile :rolleyes:

ramirez - September 6, 2005 09:32 AM (GMT)

I basically did the same as C-Man with for loop. :P

CODE

int NumOfDigits(int n) {
int d = 1;
for (; n /= 10; ++d);
return d;
}

dr voodoo - September 6, 2005 10:20 AM (GMT)

Does the minus sign count or not? I'll assume that the number of characters needed for the representation produced by printf("%i", i); is meant.

CODE

unsigned digits(int num)
{
int digits = 0;
if(num == 0)
return 1;
if(num < 0){
num = -num;
++digits; // The minus sign
}
for(;num; num /= 10)
++digits;
return digits;
}

ramirez - September 6, 2005 01:01 PM (GMT)

Well, the problem is that how many digits there are, as far as I know a minus sign isn't considered a digit.. :P
But yeah, it's a good question whether it should be counted or not.

KTC - September 6, 2005 04:23 PM (GMT)

QUOTE

Does the minus sign count or not?

The specification (problem statement) doesn't specify, so it's your job as a programmer to decide and then document the decision.

Comments on proposed solutions:
C-Man's:

CODE

while (i /= 10);

An implementation is allow to truncate the value of n/10 either up or down. So (-99)/10 can return -9 or -10. Thus your solution does not always work.

ramirez's:

CODE

for (; n /= 10; ++d);

Same problem as C-Man.

dr voodoo's:

CODE

num = -num;

A negative integer does not always have a positive corresponding absolute value that's representable, 2's complement arithmetic. If I pass INT_MIN as the argument to your function, on a lot of computers, your function wouldn't return a correct result.

CODE

return digits;

signed unsigned mismatch.

Guys, there's a reason why the signed integer version is listed as the most difficult of the three. Maybe try the simpler one first? :wink2:

myork - September 6, 2005 04:54 PM (GMT)

My first thought was:

CODE

int numberOfDigitsInInt(unsigned int x)
{
if (x < 10) return(1);
if (x < 100) return(2);
#if (sizeof(int) == 1)
return(3)
#else
if (x < 1000) return(3);
if (x < 10000) return(4);
#if (sizeof(int) == 2)
return(5);
#else
if (x < 100000) return(5);
if (x < 1000000) return(6);
if (x < 10000000) return(7);

.. etc
}

But you can not tell where to stop. How many digits an int holds depends on the platform so you don't know how many if's to add.

Thinking about this so more. You may be able to use some form of template meta program to solve that problem.

so

CODE

int numberOfDigitsInInt(unsigned int x)
{
unsigned int last = 1;
unsigned int loop = 10;
unsigned int digits = 1;

/*
* When loop skips past the maximum unsigned value it will overflow.
* This will result in loop being smaller than last
* At this point digits will have been correctly identified and we can exit the loop.
*
* For unsigned integer types,
* the C standard defines that arithmetic can never overflow (ibid, paragraph 9):
*
* [...] A computation involving unsigned operands can never overflow,
* because a result that cannot be represented by the resulting unsigned integer
* type is reduced modulo the number that is one greater than the largest value
* that can be represented by the resulting type.
*/
for(;loop > last;last = loop,loop *= 10,++digits)
{
if (x < loop) break;
}
return(digits);
}

myork - September 6, 2005 05:14 PM (GMT)

CODE

int numberOfDigitsInInt(int x)
{
unsigned int newX;
if (x < 0)
{
/*
* Can not use -x (as this will result in an integer).
* If -x can not be represented as integer it will fail (possably).
* So we compliment it first then convert it to an unsigned int.
* Thus we loose no information in any curcumstance.
*
* If C stores negative numbers as 2's compliment (need to verify this)
* then we need increment the value by 1 to get the ABS value.
* This can now be done safely as uint holds more positive values than int.
*/
newX = static_cast<unsigned int>(~x);
++newX;
}
else
{ newX = static_cast<unsigned int>(x);
}
return(numberOfDigitsInInt(newX));
}

Just guessing.

C-Man - September 6, 2005 05:33 PM (GMT)

KTC because i know 100% how x86 handles integer division i know it will allways work
on x86

KTC - September 6, 2005 05:36 PM (GMT)

I never said you're programming on / for a x86 platform. We're writing a C++ program. I wanted a C++ program that's guarantee to work based on the C++ standard, and as I told you in IRC just now, the C++ standard doesn't guarantee such division to work as you intended. ISO/IEC 14882:2003 section 5.6.4.

dorto - September 6, 2005 06:09 PM (GMT)

QUOTE (C-Man @ Sep 6 2005, 05:33 PM)

KTC because i know 100% how x86 handles integer division i know it will allways work
on x86

how x86 handles the integers is irrelevant here i guess. how C++ compiler handles that thing is more important and that you can never tell.

C-Man - September 6, 2005 07:55 PM (GMT)

So basing on that KTC , C/C++ isn't portable ? since the same operation would produce different results on different platforms ? no ?

myork - September 6, 2005 08:14 PM (GMT)

If you wonder off the edge of the well defined parts of C/C++ it becomes undefined and thus non portable. Thus when your code comes up against (or close too) the edges of the standard you need to be extra carefull.

Most normal code does not wonder around these wild and dangerouse edges. But if you start writting libraries you need to be more carefull.

KTC - September 7, 2005 01:42 AM (GMT)

myork's:
You changed your solution to the signed version after you initially posted it, cheat! :P

CODE

....
if (x < 10) return(1);
....

I'm never asking you to write a library ever, if that's your solution! :cop: :P

CODE

....
for(;loop > last;last = loop,loop *= 10,++digits)
....

That works. :) But for some reason, it feels like a hack.

CODE

....
newX = static_cast<unsigned int>(~x);
....
return(numberOfDigitsInInt(newX));

I came up with basically the same idea this afternoon, and for all practical purposes, this works (i.e. it works on every implementation that exists). However, on closer check of the C++ standard, I discovered this:

QUOTE (C++ Standard)

For unsigned character types, all possible bit patterns of the value representation represent numbers. These requirements do not hold for other types.

QUOTE (C++ Standard)

The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type,

In another word, there is no guarantee that unsigned int can hold ~x, where x is an int. So, the following sentence is not necessarily always true.

QUOTE

* This can now be done safely as uint holds more positive values than int.

Also, regarding

QUOTE

* If C stores negative numbers as 2's compliment (need to verify this)
* then we need increment the value by 1 to get the ABS value.

We have this:

QUOTE (C++ Standard)

The representations of integral types shall define values by use of a pure binary numeration system.44) [Example: this International Standard permits 2’s complement, 1’s complement and signed magnitude representations for integral types. ]

So that assumption doesn't hold either.

Anyway, the article where I got this from is here: http://www.cuj.com/documents/s=8188/cuj0402koenig/ (If you don't have an account, sign up for free 6 months membership, or use http://www.bugmenot.com/)

I'll have to think a little bit more about an solution for signed integer. -_-

myork - September 7, 2005 01:53 AM (GMT)

OK. SO the unsigned versions holds. :P
Need to think about the signed version. <_<

KTC - September 7, 2005 02:46 AM (GMT)

Got it. :)

CODE

unsigned ndigits( int n )
{
// Non-negative, just use unsigned version.
// Okay as non-negative range of int is subrange of corresponding unsigned
if( n >= 0 )
{
return ndigits( static_cast<unsigned>(n) );
}
// n is < 0
else
{
// Let x = number of digits in orginial n, #(n) number of digits in current n
// Invariant: x = count + #(n)

// Does not change #(n), so invariant holds
while( n % 10 )
{
++n;
}

unsigned count = 0;

while( n <= -10 )
{
++count;
// No rounding as n divide 10
n /= 10;
}

// #(n) must be 1
return count + 1;
}
}

dr voodoo - September 7, 2005 10:11 PM (GMT)

QUOTE (KTC @ Sep 6 2005, 04:23 PM)

dr voodoo's:

CODE

num = -num;

Correct that is a bug.

QUOTE

CODE

return digits;

signed unsigned mismatch.

It's impossible that digits contains a negative value so the implicit conversion will always do it's job correctly therefore I would not consider this as a bug. Perhaps as inconsistency in codeing style but not as a bug.

Would using the functions from <limits> be regarded as cheating? I mean one could regard them not as library funtions but as basic compiler related functions.

KTC - September 7, 2005 11:07 PM (GMT)

QUOTE (dr voodoo @ Sep 7 2005, 11:11 PM)

QUOTE

CODE

return digits;

signed unsigned mismatch.

Well, I was just pointing out the warning that a compiler will give you. :P

If this was a compitition, and I'm a judge, I guess I'll interpet the rule to mean you could use <limits>, as long as your solution, presumably doing different things according to what information the header have given you, cover all cases. But since I got this from that article, which was using it to show what lengths one would have to go to make sure an even simple program is correct, using <limits> might or might not have missed the point.

View Full Version: Solving simple problem correctly the first time