473,836 Members | 1,572 Online

# Fibonacci number

How to generate fibonacci mubers in C ?
Nov 14 '05
62 5462
Dan Pop wrote:
CBFalconer <cb********@yah oo.com> writes:
Apart from exponential notation for reals, I see no problem
building iron-clad numeric input parsers with one-char look

Dealing with overflow without invoking undefined behaviour is
the most challenging part.

Something along the lines of:

overflow = partial = 0;
while (getavaliddigit ()) {
.... form input digit ....
if ((partial < CRITERION) ||
(MAX - digit) / base) <= partial))
partial = base * partial + digit;
else {
overflow = 1;
partial = MAX;
}
}
putback(ch); /* beware complications from EOF and unget */

does not require any hardware overflow detection, and will gobble
up a stream of digits.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
Nov 14 '05 #51
"Wojtek Lerch" <Wo******@yahoo .ca> wrote:
"P.J. Plauger" <pj*@dinkumware .com> wrote in message
"CBFalconer " <cb********@yah oo.com> wrote in message
news:40******** *******@yahoo.c om...
have no problems with needing to design such routines, but I do
have problems with suddenly finding out that it is necessary.
Especially when the only change really needed is to ban the

Or skip it yourself. Why is that so hard?

Because you might not have a guarantee that the current locale is "C"?

It seems reasonable that in other locales, strtoul() might recognize
additional spellings of the negative sign, or accept the sign after the
digits. How do I tell the difference between 2 and -4294967294 then?

7.20.1.4 #6: In other than the "C" locale, additional locale-specific
subject sequence forms may be accepted.

IOW, if you're not in the "C" locale, you don't know jack about the
subject sequence anyway, so there's no way for you to tell whether
_anything_ is positive or negative - but more importantly, you don't
even know if anything is an integer in the first place.

But there's still a reasonable way around this: _first_ scan the string
with strtol(). If the result is negative, the subject sequence contained
a minus sign; this is true regardless of whether the number fits a long,
because on negative overflow, strtol() returns LONG_MIN, which is also
negative.

Richard
Nov 14 '05 #52
In <40************ ***@null.net> "Douglas A. Gwyn" <DA****@null.ne t> writes:
Dan Pop wrote:
In <AY************ ********@comcas t.com> "Douglas A. Gwyn" <DA****@null.ne t> writes:
>Really good input checking and validation requires much
>more than any Standard C library function provides.

And this is a deficiency of the C standard that the committee doesn't
bother to fix. Why should each robust C application have to invent its
own wheel?

What constitutes really good input checking and validation
is heavily application-dependent.

When dealing with numeric input, all applications have the same
requirements: the input was correct according to the specifications of
the corresponding type. If the application wants further restrictions
(e.g. values in a subrange of type_MIN..type_ MAX), these can be
trivially implemented once you know the input was valid for its
intended type.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #53
In <c1**********@s unnews.cern.ch> Da*****@cern.ch (Dan Pop) writes:
Actually, scanf is quite good and well designed. I have only two

1. Undefined behaviour on numeric input overflow. Making the conversion
fail would have been a lot more useful.

2. No escape sequence for specifying a null character in a scanset (\0
would terminate the format string).

I somehow forgot the third one: no way to dynamically specify maximum
field widths, like the asterisk in printf formats.

The workaround is to build the whole format string at run time, but
this destroys the code readability, because you have to imagine how
the format string would look like, instead of simply looking at it.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #54
P.J. Plauger <pj*@dinkumware .com> wrote:
Safety tip: Use 10 as the third (base) argument to strtoul

And not 010 :-)

-- Richard
--
Spam filter: to mail me from a .com/.net site, put my surname in the headers.

FreeBSD rules!
Nov 14 '05 #55
In <mv************ @jones.homeip.n et> la************@ ugsplm.com writes:
In comp.std.c P.J. Plauger <pj*@dinkumware .com> wrote:

Safety tip: Use 10 as the third (base) argument to strtoul, so 012
converts to 12. Don't use 0 as the base argument, since that's the
*only* form that lets the input prefix determine the base.

But again, that's application dependent. For some applications, being
able to input octal or hex in addition to decimal is definitely a
feature, not a bug.

This whole subthread was started by the complaint that 012 is interpreted
as an octal number, which I failed to understand.

If you don't want this to happen, use base 10 and it won't happen.
If you use "base" 0, it is precisely because you want this to happen.

Programs using "base" 0 should warn the users about the expected input
formats and their semantics.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 14 '05 #56
Richard Bos wrote:
"Wojtek Lerch" <Wo******@yahoo .ca> wrote:
It seems reasonable that in other locales, strtoul() might recognize
additional spellings of the negative sign, or accept the sign after the
digits. How do I tell the difference between 2 and -4294967294 then?
7.20.1.4 #6: In other than the "C" locale, additional locale-specific
subject sequence forms may be accepted.

IOW, if you're not in the "C" locale, you don't know jack about the
subject sequence anyway, so there's no way for you to tell whether
_anything_ is positive or negative - but more importantly, you don't
even know if anything is an integer in the first place.

Exactly: all I can possibly know is what strtoul() tells me. If
strtoul() tells me that the string a person entered is a
representation of the number 2 in the current locale, I have no choice
but to trust that.

Unless, of course, I parse the string myself and notice that it's
"-4294967294". But if I'm not in the "C" locale, I have no reliable
way of catching all such misunderstandin gs.
But there's still a reasonable way around this: _first_ scan the string
with strtol(). If the result is negative, the subject sequence contained
a minus sign; this is true regardless of whether the number fits a long,
because on negative overflow, strtol() returns LONG_MIN, which is also
negative.

That's a nice idea, but I think it might not work with some
conceivable (albeit wierd) implementations . Imagine, for instance,
that in some locale, the additional forms of subject sequences contain
a prefix that specifies whether the number is signed negative, signed
non-negative, or unsigned, and strtol() rejects the unsigned ones as
invalid. Wouldn't that be conforming?
Nov 14 '05 #57
Wo******@yahoo. ca (Wojtek Lerch) wrote:
Richard Bos wrote:
But there's still a reasonable way around this: _first_ scan the string
with strtol(). If the result is negative, the subject sequence contained
a minus sign; this is true regardless of whether the number fits a long,
because on negative overflow, strtol() returns LONG_MIN, which is also
negative.

That's a nice idea, but I think it might not work with some
conceivable (albeit wierd) implementations . Imagine, for instance,
that in some locale, the additional forms of subject sequences contain
a prefix that specifies whether the number is signed negative, signed
non-negative, or unsigned, and strtol() rejects the unsigned ones as
invalid. Wouldn't that be conforming?

I'm not sure, but I doubt it. Even if it is, when it returns a negative
value, the subject sequence is signed negative. Invalid subject
sequences must return 0.

Richard
Nov 14 '05 #58
Richard Bos wrote:
Wo******@yahoo. ca (Wojtek Lerch) wrote:
Richard Bos wrote:
But there's still a reasonable way around this: _first_ scan the string
with strtol(). If the result is negative, the subject sequence contained
a minus sign; this is true regardless of whether the number fits a long,
because on negative overflow, strtol() returns LONG_MIN, which is also
negative.

That's a nice idea, but I think it might not work with some
conceivable (albeit wierd) implementations . Imagine, for instance,
that in some locale, the additional forms of subject sequences contain
a prefix that specifies whether the number is signed negative, signed
non-negative, or unsigned, and strtol() rejects the unsigned ones as
invalid. Wouldn't that be conforming?

I'm not sure, but I doubt it. Even if it is, when it returns a negative
value, the subject sequence is signed negative. Invalid subject
sequences must return 0.

suffix that is interpreted as a negative sign by strtol(), but not
recognized by strtoul(). Can you find any words in the standard that
forbid this?...
Nov 14 '05 #59
Wo******@yahoo. ca (Wojtek Lerch) wrote:
suffix that is interpreted as a negative sign by strtol(), but not
recognized by strtoul(). Can you find any words in the standard that
forbid this?...

Not words, exactly, but it does seem to imply that. All four of
strtol(), strtoul(), strtoll() and strtoull() share a paragraph, and
that paragraph mentions "the" subject sequence, singular. The only
difference that is explicitly mentioned is that between the type to
which these functions convert the subject sequence.

Richard
Nov 14 '05 #60

This thread has been closed and replies have been disabled. Please start a new discussion.