Arithmetic problem

[Schizoid Man]

Hi,

I have a very strange arithmetic problem in C:

double t = 0.1;
int steps = 10;
double time_step = t / (double)steps;

I would expect the output of time_step to be 0.01000 (my output is of
the form %5.5f), but instead it a very large (and incorrect) negative
number.

Any ideas?

Thanks,
Schiz

[Richard Heathfield]

Schizoid Man said:

Coos Haak wrote:

On another note, can you tell me why the following method are not giving
me Combination results over 12? The following program works fine till 12
and then mysteriously blows up.
12 factorial can fit in 32 bits. 13 factorial won't.

Hi Coos,

I figured that out, albeit after I posted my message.

The function I'm trying to evaluate is Combin(n,r) = factorial(n) /
(factorial (n-r) * factorial (r)).

For some reason, C is blowing up for numbers like Combin(350,170) ,

You reckon? :-)
whereas Excel is computing these large numbers quite easily. Any
suggestions?

It isn't C that's blowing up. It's your program that's blowing up.

When you're dealing with huge numbers, you have to box clever. The Excel
programmers, it seems, have done so, and you have to do that too.

Let's take a smaller example than C(350,170). Say, C(15,5).

Using your method, the first thing you calculate is 15!, which is
1307674368000, which is way too big to fit into a 32-bit integer.

But you don't have to do it like that.

C(15,5) = 15! / ((15-5)! * 5!), which is 15! / (10! * 5!)

Let's write this out in full:

15*14*13*12*11* 10*9*8*7*6*5*4* 3*2*1
-----------------------------------
10*9*8*7*6*5*4* 3*2*1 * 5*4*3*2*1

Cancel 10!, leaving:

15*14*13*12*11
--------------
5*4*3*2*1

Cancel 15s:

14*13*12*11
--------------
4*2*1

Cancel 4s:

14*13*3*11
--------------
2*1

Cancel 2s:

7*13*3*11

This comes to 3003, which is easily within the range of int, and we got
there without having to over-burden any ints with colossal out-of-range
numbers.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Schizoid Man]

Richard Heathfield wrote:

Schizoid Man said: This comes to 3003, which is easily within the range of int, and we got
there without having to over-burden any ints with colossal out-of-range
numbers.

Hi Richard,

Absolutely right - it's my program that's blowing up. I am evaluation
C(n,r) as n*(n-1)*...*(n-r+1) / r!

However, it seems that even the above expression could use a lot of
optimization.

Thanks for the input.

[Martin Ambuhl]

Schizoid Man wrote:

Hi,

I have a very strange arithmetic problem in C:

double t = 0.1;
int steps = 10;
double time_step = t / (double)steps;

I would expect the output of time_step to be 0.01000 (my output is of
the form %5.5f), but instead it a very large (and incorrect) negative
number.

Any ideas?

I suspect that you have misidentified your problem. It's impossible to
tell, since you have not given us compilable code that exhibits your
problem. Try the following, and tell us what happens:

#include <stdio.h>

int main(void)
{
double t = 0.1;
int steps = 10;
double time_step = t / /* unnecessary (double) */ steps;
printf("%5.5f\n ", time_step);
return 0;
}

When I run the code above, I get:
0.01000

What do you get?

[CBFalconer]

Schizoid Man wrote:

.... snip ...
scanf_s is a method that replaces scanf in the new Visual C++,
scanf has been deprecated. Similarly, for the tchar.h file too.

Don't let yourself be brain washed by Micro$loth. scanf has NOT
been deprecated. scanf_s is NOT a method, it is a non-standard
function. There is a draft technical report n1146.pdf describing
these things.

Using such non-standard things, and such other non-standards as
stdafx.h, only locks your code into the Micro$oft way and is
counter-productive.

--
Some informative links:
news:news.annou nce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

[CBFalconer]

Richard Heathfield wrote:

Schizoid Man said:

Coos Haak wrote:

On another note, can you tell me why the following method are
not giving me Combination results over 12? The following program
works fine till 12 and then mysteriously blows up.

12 factorial can fit in 32 bits. 13 factorial won't.

I figured that out, albeit after I posted my message.

The function I'm trying to evaluate is Combin(n,r) = factorial(n) /
(factorial (n-r) * factorial (r)).

For some reason, C is blowing up for numbers like Combin(350,170) ,

You reckon? :-)

whereas Excel is computing these large numbers quite easily. Any
suggestions?

It isn't C that's blowing up. It's your program that's blowing up.

When you're dealing with huge numbers, you have to box clever. The
Excel programmers, it seems, have done so, and you have to do that
too.

Let's take a smaller example than C(350,170). Say, C(15,5).

Using your method, the first thing you calculate is 15!, which is
1307674368000, which is way too big to fit into a 32-bit integer.

But you don't have to do it like that.

C(15,5) = 15! / ((15-5)! * 5!), which is 15! / (10! * 5!)

Let's write this out in full:

15*14*13*12*11* 10*9*8*7*6*5*4* 3*2*1
-----------------------------------
10*9*8*7*6*5*4* 3*2*1 * 5*4*3*2*1

Cancel 10!, leaving:

15*14*13*12*11
--------------
5*4*3*2*1

Cancel 15s:

14*13*12*11
--------------
4*2*1

Cancel 4s:

14*13*3*11
--------------
2*1

Cancel 2s:

7*13*3*11

This comes to 3003, which is easily within the range of int, and
we got there without having to over-burden any ints with colossal
out-of-range numbers.

As an example of extending usable ranges, especially for
factorials, here is something I cooked up a few years ago:

/* compute factorials, extended range
on a 32 bit machine this can reach fact(15) without
unusual output formats. With the prime table shown
overflow occurs at 101.

Public domain, by C.B. Falconer. 2003-06-22
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* 2 and 5 are handled separately
Placing 2 at the end attempts to preserve such factors
for use with the 5 factor and exponential notation
*/
static unsigned char primes[] = {3,7,11,13,17,1 9,23,29,31,37,
41,43,47,53,57, 59,61,67,71,
/* add further primes here -->*/
2,5,0};
static unsigned int primect[sizeof primes]; /* = {0} */

static double fltfact = 1.0;

static
unsigned long int fact(unsigned int n, unsigned int *zeroes)
{
unsigned long val;
unsigned int i, j, k;

#define OFLOW ((ULONG_MAX / j) < val)

/* This is a crude mechanism for passing back values */
for (i = 0; i < sizeof primes; i++) primect[i] = 0;

for (i = 1, val = 1UL, *zeroes = 0; i <= n; i++) {
fltfact *= i; /* approximation */
j = i;
/* extract exponent of 10 */
while ((0 == (j % 5)) && (!(val & 1))) {
j /= 5; val /= 2;
(*zeroes)++;
}
/* Now try to avoid any overflows */
k = 0;
while (primes[k] && OFLOW) {
/* remove factors primes[k] */
while (0 == (val % primes[k]) && OFLOW) {
val /= primes[k];
++primect[k];
}
while (0 == (j % primes[k]) && OFLOW) {
j /= primes[k];
++primect[k];
}
k++;
}

/* Did we succeed in the avoidance */
if (OFLOW) {
#if DEBUG
fprintf(stderr, "Overflow at %u, %lue%u * %u\n",
i, val, *zeroes, j);
#endif
val = 0;
break;
}
val *= j;
}
return val;
} /* fact */

int main(int argc, char *argv[])
{
unsigned int x, zeroes;
unsigned long f;

if ((2 == argc) && (1 == sscanf(argv[1], "%u", &x))) {
if (!(f = fact(x, &zeroes))) {
fputs("Overflow \n", stderr);
return EXIT_FAILURE;
}

printf("Factori al(%u) == %lu", x, f);
if (zeroes) printf("e%u", zeroes);
for (x = 0; primes[x]; x++) {
if (primect[x]) {
printf(" * pow(%d,%d)", primes[x], primect[x]);
}
}
putchar('\n');
printf("or approximately %.0f.\n", fltfact);
return 0;
}
fputs("Usage: fact n\n", stderr);
return EXIT_FAILURE;
} /* main */

--
Some informative links:
news:news.annou nce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

[Schizoid Man]

CBFalconer wrote:

As an example of extending usable ranges, especially for
factorials, here is something I cooked up a few years ago:

Thank you very much for the example. You're absolutely right about
non-standard libraries and methods, but I just want to get up and
running with C in time for this interview.

I'm having another odd problem. In the following funcation, I am trying
to dimension an array declaration using a value that is passed to the
function.

double treeNPV(int steps) {

const int array_dim = steps;
double s_price[array_dim][array_dim];

}

However, I get the following compile errors:
- cannot allocate an array of constant size 0
- expected constant expression

The code looks correct. Or am I missing something very basic again?

Thank you.

[Robert Gamble]

Schizoid Man wrote:

CBFalconer wrote:

As an example of extending usable ranges, especially for
factorials, here is something I cooked up a few years ago:
Thank you very much for the example. You're absolutely right about
non-standard libraries and methods, but I just want to get up and
running with C in time for this interview.

Have you read the C FAQ yet? I would strongly recommend that you do so
and try to inderstand as much as possible before your interview, it is
available at <http://c-faq.com/>.
I'm having another odd problem. In the following funcation, I am trying
to dimension an array declaration using a value that is passed to the
function.

double treeNPV(int steps) {

const int array_dim = steps;
double s_price[array_dim][array_dim];

}

However, I get the following compile errors:
- cannot allocate an array of constant size 0
- expected constant expression

The code looks correct. Or am I missing something very basic again?

Prior to C99 the size of an array had to be specified using an integer
constant expression (sometimes referred to as ICE). Despite
appearances, a "const" qualified type is not a constant expression in
C, see FAQ question 11.8. C99 introduced variable length arrays (VLAs)
removing the constant expression requirement, your compiler apparently
doesn't support them (or at least not in the mode in which you are
invoking it). In any case, arrays in C must have a size greater than 0
so you should validate array_dim before using it to declare s_price.

Robert Gamble

[Schizoid Man]

Robert Gamble wrote:

Schizoid Man wrote: Have you read the C FAQ yet? I would strongly recommend that you do so
and try to inderstand as much as possible before your interview, it is
available at <http://c-faq.com/>.

Hi Robert,

I'll take a look at it. Probably more useful that inundating this forum.

It's not a programming job, though the interview will test some computer
science and I believe C is the language of choice. Unfortunately, I am
an Excel/VBA/VB monkey at work, so my C is rusty at best.

Thank you for the suggestion.

[ken]

this is the simple program sohwin u r problem
but i go the correct answer....

#include<stdio. h>
int main()
{
double t = 0.1;
int steps = 10;
double time_step = t / (double)steps;
printf("%5.5f\n ", time_step);
return 0;
}

the output of this prog is 0.01000

[Richard Tobin]

In article <e5**********@g eraldo.cc.utexa s.edu>,
Schizoid Man <sc***@sf.com > wrote:

scanf_s is a method that replaces scanf in the new Visual C++, scanf has
been deprecated. Similarly, for the tchar.h file too.

Microsoft can "deprecate" whatever it likes, if but you follow them
you will restrict your code to Microsoft operating systems.

-- Richard