C++ Learning Community -> Solving simple problem correctly the first time

On Suday the 11th of February, 2007 -after 3 and a half years on InvisionFree, we have moved! This old board remains as a read only archive of years past, and registration has been disabled here. All new and current members should register at http://www.cpplc.net/forum .

Solving simple problem correctly the first time, A challenge

Track this topic | Email this topic | Print this topic

KTC

Posted: Sep 6 2005, 07:13 AM

std::freak

Group: Members
Posts: 1,465
Member No.: 420
Joined: 30-December 03

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.

--------------------

Say NO to software patents !!

Newbie-FAQ : Archive of Informative Topics

The D Programing Language : High Level Assembly

C-Man

Posted: Sep 6 2005, 09:14 AM

Lazy bum

Group: Super Moderator
Posts: 4,563
Member No.: 609
Joined: 29-February 04

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

--------------------

ramirez

Posted: Sep 6 2005, 09:32 AM

geekoid

Group: Members
Posts: 403
Member No.: 1,218
Joined: 18-February 05

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

Posted: Sep 6 2005, 10:20 AM

c++ programmer

Group: Super Moderator
Posts: 1,986
Member No.: 11
Joined: 23-June 03

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;
}

--------------------

Conscience doesn't really keep you from doing anything wrong -- it merely keeps you from enjoying it.

My Site
My Tutorial

ramirez	Posted: Sep 6 2005, 01:01 PM
geekoid Group: Members Posts: 403 Member No.: 1,218 Joined: 18-February 05	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

Posted: Sep 6 2005, 04:23 PM

std::freak

Group: Members
Posts: 1,465
Member No.: 420
Joined: 30-December 03

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?

--------------------

Say NO to software patents !!

Newbie-FAQ : Archive of Informative Topics

The D Programing Language : High Level Assembly

myork

Posted: Sep 6 2005, 04:54 PM

c++ guru

Group: Super Moderator
Posts: 2,584
Member No.: 487
Joined: 21-January 04

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

Posted: Sep 6 2005, 05:14 PM

c++ guru

Group: Super Moderator
Posts: 2,584
Member No.: 487
Joined: 21-January 04

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	Posted: Sep 6 2005, 05:33 PM
Lazy bum Group: Super Moderator Posts: 4,563 Member No.: 609 Joined: 29-February 04	KTC because i know 100% how x86 handles integer division i know it will allways work on x86 --------------------

KTC	Posted: Sep 6 2005, 05:36 PM
std::freak Group: Members Posts: 1,465 Member No.: 420 Joined: 30-December 03	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. -------------------- Say NO to software patents !! Newbie-FAQ : Archive of Informative Topics The D Programing Language : High Level Assembly

dorto

Posted: Sep 6 2005, 06:09 PM

geek

Group: Members
Posts: 268
Member No.: 1,143
Joined: 20-December 04

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.

--------------------

dorto

Absolute Beginner(programming): 'You Can Do It' by Francis Glassborow
Absolute Beginner(c++): 'Accelerated C++' by Andrew Koenig and Barbara Moo
Free Online Book: http://mindview.net/Books/TICPP/ThinkingInCPP2e.html
C++ Bible: 'The C++ Programming Language' by Bjarne Stroustrup

C-Man	Posted: Sep 6 2005, 07:55 PM
Lazy bum Group: Super Moderator Posts: 4,563 Member No.: 609 Joined: 29-February 04	So basing on that KTC , C/C++ isn't portable ? since the same operation would produce different results on different platforms ? no ? --------------------

myork	Posted: Sep 6 2005, 08:14 PM
c++ guru Group: Super Moderator Posts: 2,584 Member No.: 487 Joined: 21-January 04	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

Posted: Sep 7 2005, 01:42 AM

std::freak

Group: Members
Posts: 1,465
Member No.: 420
Joined: 30-December 03

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

CODE

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

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

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.

--------------------

Say NO to software patents !!

Newbie-FAQ : Archive of Informative Topics

The D Programing Language : High Level Assembly

myork	Posted: Sep 7 2005, 01:53 AM
c++ guru Group: Super Moderator Posts: 2,584 Member No.: 487 Joined: 21-January 04	OK. SO the unsigned versions holds. Need to think about the signed version.

« Next Oldest | C++ Tips | Next Newest »

Fully Featured & Customizable Free Forums

Learn More · Sign-up Now