In article , curien@cox.net
says...
[ ... ]
> For what definition of complex? Implementing your algorithm correctly
> requires either a) external libraries or b) lots of non-trivial string
> manipulation.
Only when/if you define "correctly" in your own particular way -- i.e.
that the number _will_ exceed the limits of a long long, even though
I've already shown that doing so is far beyond utterly pointless.
> Your solution was four lines of code. My solution was about twice as long,
> but only because I split up a mathematical expression into several
> statements. My version could be five lines, easily. (In both cases, I did
> not count declaration statements.)
>
> > Question: does it provide any useful capabilities to compensate for
> > its extra complexity?
>
> Again, what complexity?
You've admitted that it's twice as long, and even if you compacted it
(at the expense of obfuscation) it would _still_ be longer, and you fail
to see the extra complexity? For that matter, if I wanted to compact
the code at the expense of obfuscation, mine would be TWO lines long
(and still not _particularly_ difficult to understand).
> > Answer: NO!
>
> YES!
>
> My version (which uses the same algorithm as David's) does not have any
> artificial limits (such as the size of a long or the precision of a double).
The size of a long long is hardly an "artificial limitation" -- as I
already pointed out, even if you sold tickets at a rate of a million per
second (which I'm quite certain is FAR faster than is really possible) a
64-bit integer is sufficient to last for over half a million years...
The original specification said that the number would be large, but NOT
that it would necessarily exceed the range of a long long (for example).
To make a statement that my solution is incorrect, you need certainty
that the numbers WILL do exactly that -- despite the fact that trivial
math proves there's absolutely NO reason to do so at all.
> IOW, mine is correct, and yours is not. Is not one line's worth of code
> complexity a small price to pay for correctness?
IF your's was correct and mine wasn't, it would be. So far, nothing of
the sort has been shown, and simple math proves that there's no reason
for it.
> Implement your algorithm without the above-mentioned artificial limits,
> and then we'll compare the code complexity of the two.
They aren't artificial limits at all -- I'll tell you what: figure up
the volume of the atmosphere of the earth, and figure up the average
volume of space occupied by a single plane. Assume that we keep the
entire atmosphere full of airplanes all the time, and that EVERY one is
completely full all the time, and a separate ticket is sold to each
passenger on every flight, and tell us how many years it would take to
use up the 64-bit numbers, even at that absolute maximum rate could
_possibly_ do so.
The fact is, thinking that there's any conceivable reason for using more
than a 64-bit number shows only that you haven't a clue in the world of
how large a range 64 bits really has.
If we stick to more practical limits, like the number of tickets that
are really being sold, and the maximum rate of possible growth (keep in
mind that building things like airports and large airplanes takes time),
32-bit numbers still do NOT impose any sort of artificial limit.
The bottom line is that the limits involved are NOT in my algorithm at
all: they're in the situation originally being addressed. You can
squirm as long as you want to, but you can't change the fact that
there's NO real reason for airline ticket serial numbers to cover a
range larger than a 64-bit number provides.
--
Later,
Jerry.
The universe is a figment of its own imagination.
In article <6d8002d0.0309101459.1dfbd21b@posting.google.com>,
deane_gavin@hotmail.com says...
> Jerry Coffin wrote in message news:...
> > In article ,
> > no@email.provided says...
> >
> > [ ... ]
> >
> > > You don't need to store any digits.
> >
> > Despite your cleverness, you've yet to show this.
>
> Each iteration of David's while loop reads a digit. The previously
> read digit is not remembered. QED
....and as-is, it doesn't work correctly. See if you can make it work
correctly without storing at least one extra digit.
> > You're running into the same basic problem many people do when they
> > start to learn a few cute algorithms: they want to apply those
> > algorithms everywhere, whether they're applicable or not.
>
> Didn't look that way to me.
Then you didn't look very carefully.
[ ... ]
> Your solution can't cope if the number doesn't fit in the largest
> integer type available. It's not unusual for this limit to be 32 bits
> and the ticket number in the OP's example is longer than this. Is your
> objection solely based on the fact that _if_ 64 bit integers are
> available without resorting to a bignum class, David's algorithm is
> redundant?
The title line says "[C]". The C standard specifies that there IS a
type named long long, and its range requires 64 bits to represent.
IOW, if there isn't a 64-bit type available, then what you're working
with is NOT a C compiler.
> > Your original statement was wrong: it's not easier to process the input
> > one digit at a time. While you've shown a way it COULD be done, the way
> > you've shown clearly leads to MORE complex code.
>
> Maybe not easier, just necessary.
Rather the contrary -- not necessary at all, unless you postulate a
serial number drastically larger than any for which there's any
conceivable use.
--
Later,
Jerry.
The universe is a figment of its own imagination.
In article ,
no@email.provided says...
[ ... ]
> Here is the conversation again, without the edits:
Gee...it doesn't look like "without the edits" at all to me -- you've
left out nearly all the context in which the conversation took place.
[ ... ]
> It seemed to me that you were referring only to the part of the exercise
> requiring calculation of the remainder of the division. For that part, you
> don't need to store any digits.
It seems to me that the original question was about solving a specific
problem. You asserted that it could be done without storing any digits,
withOUT specifying that what you were solving was really only a problem
you'd invented yourself, that was (at most) only somewhat related to the
original problem.
[ ... ]
> > > Execution time is irrelevant.
> >
> > Says who?
>
> Says the exercise. The requirement was to "Write a program that checks
> whether or not an airline ticket number is valid:". It doesn't say to write
> the fastest possible program. It doesn't say there are any bonus marks for
> speed. It's just asking to get the job done.
It also doesn't say "execution time is irrelevant" or anything like it.
In short, you've simply assumed it's irrelevant.
> I wasn't trying to. I was responding to your posts, which confined
> themselves to discussion of the division part of the problem.
No, they did not. My posts discussed the entire problem. Absolutely
nowhere, in any post, have I said a single word about restricting my
comments to anything less than the entire problem.
> The problem does not specify a ticket-number length. Therefore, you can't
> guarantee that your code will work.
If you're going to try to postulate nonsense, then you can't guarantee
that your's will work either -- just for example, if the number was long
enough, all energy in the universe might be used up before you finished
reading all the digits.
Of course, postulating that the number would really be that large is
utterly nonsensical -- just like exceeding 64 bits is.
> It also doesn't satisfy the hint given:
> Hint: Don't attempt to read the number in a single step. Instead,
> use getchar to obtain its digits one by one. Carry out the
> division on its digits one at a time, being careful not to include
> the last digit in the division
>
> Even if you argue that this is just a hint, the exercise evidently wants the
> student to solve the problem this way.
What's truly evident is that the person who posed the problem did not
think it through very well, and ended up giving a lousy definition of
the problem. The hint is probably even worse.
In the end, you're left with a choice: do the job well, or give the
instructor what he wants. The two aren't necessarily the same.
[ ... ]
> Are you sure that all airline tickets for which your code might be used will
> fit into a long, or even a double? I'm not.
I'm absolutely certain there's no reason for them to exceed what can be
stored in a long long or a double. Given the lousy definition of the
original problem, we're left with few guarantees of anything, so we're
forced to make some assumptions about what's reasonable. Lest you
should claim that you made no such assumptions, I'll point out that (for
example) you assumed the number would be base 10 (as I also did).
That's an assumption I'm perfectly willing to admit is entirely
reasonable, but it's an assumption nonetheless.
To make a long story short, we've both made reasonable assumptions.
You've then tried to claim that one of my assumptions was not
reasonable, even though a few seconds of math would thoroughly disprove
such a claim.
--
Later,
Jerry.
The universe is a figment of its own imagination.
In article , curien@cox.net
says...
[ ... ]
> My version (which uses the same algorithm as David's) does not have any
> artificial limits (such as the size of a long or the precision of a double).
>
> IOW, mine is correct, and yours is not. Is not one line's worth of code
> complexity a small price to pay for correctness?
Doing a bit more checking, I've found that in fact the number is always
10 digits -- which is guaranteed to fit into either a long long or a
double.
In short, your assertion is wrong: my method is guaranteed to work.
--
Later,
Jerry.
The universe is a figment of its own imagination.
Jerry Coffin wrote in message
news:MPG.19c9ad534de249e19896b3@news.west.earthlink.net...
> In article , curien@cox.net
> says...
>
> [ ... ]
>
> > My version (which uses the same algorithm as David's) does not have any
> > artificial limits (such as the size of a long or the precision of a
double).
> >
> > IOW, mine is correct, and yours is not. Is not one line's worth of code
> > complexity a small price to pay for correctness?
>
> Doing a bit more checking, I've found that in fact the number is always
> 10 digits --
What number?
> which is guaranteed to fit into either a long long or a
> double.
>
> In short, your assertion is wrong: my method is guaranteed to work.
See how it goes with this:
76562091829833252963
DW
Jerry Coffin wrote in message
news:MPG.19c9a2baf8d867ea9896b0@news.west.earthlink.net...
[snip]
I stand by all my words up to this point. Readers, if there are any left,
are welcome to consider your words and mine and come to whatever conclusion
they like.
> I'm absolutely certain there's no reason for them to exceed what can be
> stored in a long long or a double.
And how do you reconcile that and the hint to solve the division one
character at a time? What need is there for a long long or a double to even
enter the problem-poser's mind if it is to be solved that way?
> Given the lousy definition of the
> original problem,
It looks quite okay to me.
> we're left with few guarantees of anything, so we're
> forced to make some assumptions about what's reasonable. Lest you
> should claim that you made no such assumptions, I'll point out that (for
> example) you assumed the number would be base 10 (as I also did).
> That's an assumption I'm perfectly willing to admit is entirely
> reasonable, but it's an assumption nonetheless.
>
> To make a long story short, we've both made reasonable assumptions.
I don't accept that your assumptions were reasonable, given the wording of
the problem.
> You've then tried to claim that one of my assumptions was not
> reasonable,
Right.
> even though a few seconds of math would thoroughly disprove
> such a claim.
I don't see how.
DW
Jerry Coffin wrote in message news:...
> In article <6d8002d0.0309101459.1dfbd21b@posting.google.com>,
> deane_gavin@hotmail.com says...
> > Jerry Coffin wrote in message news:...
> > > In article ,
> > > no@email.provided says...
> > >
> > > [ ... ]
> > >
> > > > You don't need to store any digits.
> > >
> > > Despite your cleverness, you've yet to show this.
> >
> > Each iteration of David's while loop reads a digit. The previously
> > read digit is not remembered. QED
>
> ...and as-is, it doesn't work correctly. See if you can make it work
> correctly without storing at least one extra digit.
I read this sub-thread exactly as David did, ie that you were talking
about the division part of the problem only. Which David solved.
> > Your solution can't cope if the number doesn't fit in the largest
> > integer type available. It's not unusual for this limit to be 32 bits
> > and the ticket number in the OP's example is longer than this. Is your
> > objection solely based on the fact that _if_ 64 bit integers are
> > available without resorting to a bignum class, David's algorithm is
> > redundant?
>
> The title line says "[C]". The C standard specifies that there IS a
> type named long long, and its range requires 64 bits to represent.
>
> IOW, if there isn't a 64-bit type available, then what you're working
> with is NOT a C compiler.
OK, so we can assume 64 bits are available. Why can we also assume
that no airline will choose to use a 20 digit ticket number? All my
credit and bank cards have 16 digit numbers, plus (these days) three
security digits. This will just fit in 64 bits. But by your argument,
because it would take nearly a third of a million years to use up all
the available numbers at one million per second, the banks are being
non-sensical and satisfying their requirements is irrelevant.
If I habitually ignored all the unexpected behaviour from the people
who use my software I would have been out of a job a long time ago.
> > > Your original statement was wrong: it's not easier to process the input
> > > one digit at a time. While you've shown a way it COULD be done, the way
> > > you've shown clearly leads to MORE complex code.
> >
> > Maybe not easier, just necessary.
>
> Rather the contrary -- not necessary at all, unless you postulate a
> serial number drastically larger than any for which there's any
> conceivable use.
See above. The customer pays my wages. Unless they have signed a piece
of paper accepting that 20 digit serial numbers will not work, I
produce code that can cope with that.
GJD
On Thu, 11 Sep 2003 03:40:05 +0000, Jerry Coffin wrote:
> In article , curien@cox.net
> says...
>
> [ ... ]
>
>> For what definition of complex? Implementing your algorithm correctly
>> requires either a) external libraries or b) lots of non-trivial string
>> manipulation.
>
> Only when/if you define "correctly" in your own particular way -- i.e.
> that the number _will_ exceed the limits of a long long, even though
> I've already shown that doing so is far beyond utterly pointless.
>
>> Your solution was four lines of code. My solution was about twice as long,
>> but only because I split up a mathematical expression into several
>> statements. My version could be five lines, easily. (In both cases, I did
>> not count declaration statements.)
>>
>> > Question: does it provide any useful capabilities to compensate for
>> > its extra complexity?
>>
>> Again, what complexity?
>
> You've admitted that it's twice as long, and even if you compacted it
> (at the expense of obfuscation) it would _still_ be longer, and you fail
> to see the extra complexity?
Yes. "Twice as long" is still only a few lines. It's not a long algorithm,
and not particularly complex. Most people learn it in school when they're
nine years old.
> For that matter, if I wanted to compact
> the code at the expense of obfuscation,
I'd say not obfuscation, but rather style. It's a difference of
ret *= 10;
ret += ch - '0';
ret %= 7;
which is quite long-winded, versus
ret = 10 * (ch - '0' + ret) % 7;
which is not particularly obfuscated.
> mine would be TWO lines long
> (and still not _particularly_ difficult to understand).
>
>> > Answer: NO!
>>
>> YES!
>>
>> My version (which uses the same algorithm as David's) does not have any
>> artificial limits (such as the size of a long or the precision of a double).
>
> The size of a long long is hardly an "artificial limitation"
Yes, it is. Just because you think it's a /reasonable/ artificial
limitation does not make it not artificial. I don't even think it's
reasonable.
> -- as I
> already pointed out, even if you sold tickets at a rate of a million per
> second (which I'm quite certain is FAR faster than is really possible) a
> 64-bit integer is sufficient to last for over half a million years...
Or if they're a generated by some algorithm. You're assuming things all
over the place... now you're assuming that the ticket numbers are
generated sequentially. What if a sizable chunk of the numbers indicate,
say, the arriving airport, the destination airport, the cashier ID, etc. A
64-bit int can only hold 20 decimal digits... we might be down to 5 now.
At a rate of one ticket sold per second, that will run out in a little
over one day.
> The original specification said that the number would be large, but NOT
> that it would necessarily exceed the range of a long long (for example).
You're right -- it said /nothing/ about the size of the sequence. So why
are you placing artificial restrictions on it?
> To make a statement that my solution is incorrect, you need certainty
> that the numbers WILL do exactly that
No, you only need a lack of certainty that they /won't/.
> The fact is, thinking that there's any conceivable reason for using more
> than a 64-bit number shows only that you haven't a clue in the world of
> how large a range 64 bits really has.
No, it only proves that you're trying to justify an
unreasonable assumption.
> If we stick to more practical limits, like the number of tickets that
> are really being sold, and the maximum rate of possible growth (keep in
> mind that building things like airports and large airplanes takes time),
> 32-bit numbers still do NOT impose any sort of artificial limit.
Three digits for departing airport, three for arriving airport, two for
airline ID, five for travel agency ID. Oops! There's no more digits left!
> The bottom line is that the limits involved are NOT in my algorithm at
> all: they're in the situation originally being addressed.
No, they're not. Please indicate the part of the problem description where
it specifies a maximum number of digits to process. It doesn't, therefor
you cannot assume one, no matter how "reasonable" the assumption seems.
Josh
On Thu, 11 Sep 2003 07:26:34 -0400, Josh Sebastian wrote:
> You're right -- it said /nothing/ about the size of the sequence. So why
> are you placing artificial restrictions on it?
I take that back: it said one thing about the size of the sequence. It
said they were "lengthy identifying numbers". The example given doesn't
even fit into an unsigned long. It would fit into an unsigned long long,
but it was only an example; actual data might be longer.
Josh
In article ,
no@email.provided says...
[ ... ]
> > Doing a bit more checking, I've found that in fact the number is always
> > 10 digits --
>
> What number?
An airline ticket number, obviously!
> > which is guaranteed to fit into either a long long or a
> > double.
> >
> > In short, your assertion is wrong: my method is guaranteed to work.
>
> See how it goes with this:
> 76562091829833252963
That number simply isn't allowed as an airline ticket number.
--
Later,
Jerry.
The universe is a figment of its own imagination.
Mega Search
Sign Up 
