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 .


Join the millions that use us for their forum communities. Create your own forum today.
InvisionFree - Free Forum Hosting
Welcome to C++ Learning Community. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Name:   Password:

Please help out
Google

Pages: (2) [1] 2  ( Go to first unread post ) Reply to this topicStart new topicStart Poll

> Solving simple problem correctly the first time, A challenge
KTC
Posted: Sep 6 2005, 07:13 AM
Quote Post


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.


--------------------
PMUsers Website
Top
C-Man
Posted: Sep 6 2005, 09:14 AM
Quote Post


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 rolleyes.gif


--------------------
user posted image
PMEmail PosterUsers Website MSN
Top
ramirez
Posted: Sep 6 2005, 09:32 AM
Quote Post


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;
}
PMEmail Poster
Top
dr voodoo
Posted: Sep 6 2005, 10:20 AM
Quote Post


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
PMEmail PosterUsers Website
Top
ramirez
Posted: Sep 6 2005, 01:01 PM
Quote Post


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.
PMEmail Poster
Top
KTC
Posted: Sep 6 2005, 04:23 PM
Quote Post


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? wink.gif


--------------------
PMUsers Website
Top
myork
Posted: Sep 6 2005, 04:54 PM
Quote Post


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);
}
PMEmail Poster
Top
myork
Posted: Sep 6 2005, 05:14 PM
Quote Post


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.
PMEmail Poster
Top
C-Man
Posted: Sep 6 2005, 05:33 PM
Quote Post


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


--------------------
user posted image
PMEmail PosterUsers Website MSN
Top
KTC
Posted: Sep 6 2005, 05:36 PM
Quote Post


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.


--------------------
PMUsers Website
Top
dorto
Posted: Sep 6 2005, 06:09 PM
Quote Post


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
PMEmail Poster
Top
C-Man
Posted: Sep 6 2005, 07:55 PM
Quote Post


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 ?


--------------------
user posted image
PMEmail PosterUsers Website MSN
Top
myork
Posted: Sep 6 2005, 08:14 PM
Quote Post


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.
PMEmail Poster
Top
KTC
Posted: Sep 7 2005, 01:42 AM
Quote Post


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! tongue.gif
CODE
....
if (x < 10)  return(1);
....
I'm never asking you to write a library ever, if that's your solution! cop.gif tongue.gif
CODE
....
for(;loop > last;last = loop,loop *= 10,++digits)
....
That works. smile.gif 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. sleep.gif


--------------------
PMUsers Website
Top
myork
Posted: Sep 7 2005, 01:53 AM
Quote Post


c++ guru


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



OK. SO the unsigned versions holds. tongue.gif
Need to think about the signed version. dry.gif
PMEmail Poster
Top
« Next Oldest | C++ Tips | Next Newest »
InvisionFree - Free Forum Hosting
InvisionFree gives you all the tools to create a successful discussion community.
Learn More · Sign-up for Free

Topic OptionsPages: (2) [1] 2  Reply to this topicStart new topicStart Poll


Skin selector developed by XJONX. Skins created by various members of the IF Skin Zone and InvisionFree Skinning

Please help out
Hosted for free by InvisionFree* (Terms of Use: Updated 2/10/2010) | Powered by Invision Power Board v1.3 Final © 2003 IPS, Inc.
Page creation time: 0.2334 seconds | Archive