tech-userlevel archive

# Re: CVS commit: src/games/factor

```Joerg Sonnenberger <joerg%britannica.bec.de@localhost> writes:

> On Mon, May 17, 2010 at 02:53:40AM +0400, Aleksej Saushev wrote:
>> Consider natural numbers as finite cardinals, the way set theorists do.
>> Factorization of a number a is non-empty set {<f_i, n_i>} (f_i are distinct)
>> such that product f_i^n_i = a.
>
> That's a product decomposition. The term "factorisation" is after all
> refering to a specific decomposition with additional requirements on the
> f_i.

That's matter of wording lying in pure linguistics, you use two different
words of Latin origin and in my regular life I use one word of Russian origin.

>> It is easy to see that there exist numbers
>> which occur in any their factorization. These are called "prime" numbers.
>
> That's not the definition of prime elements algebra uses, which is the
> relevant field here. The algebraic definition of prime explicitly
> excludes units.

There's no algebra here, it is arithmetics, algebra may be relevant here,
but it isn't to a large extent.

>> And zero and unit are among them. Note that you have to introduce
>> "non-empty" to treat unit rather than zero. That makes zero no less
>> prime than anything else and even a bit more prime than unit.
>
> The definition of prime also excludes 0 for the simple reason that 0
> doesn't have any divisor in an integral domain like we are using here.

Who are "we"? We're using "product decomposition," and 0 can be decomposed.
Also 0 can be divisor and is divisor of 0, that you restrict yourself to
elementary school definition of divisor proves my argument that you don't
evaluate ex cathedra arguments you were once told.

> As I said originally, 0 as prime doesn't make sense at all as the
> criterion for primality, both the high school version (only dividable by
> 1 and itself) and algebraic version (not 0, not a unit, f it divides a
> product it divides it least one of the factors) fail, if only due to the
> lack of zero divisors..

And I said originally that it makes perfect sense to consider 0 as prime number,
the construction is here. Refering to high school doesn't prove anything,
because there exist different schools, and you can easily find schools using
different definitions for natural numbers and algebraic structures.
What does matter is logical argumentation rather than using advantages
of the first move.

>> When you construct integer numbers, you see that the same applies to "-1".
>> That you prefer to choose "2" as prime rather than "-2" happens due to the
>> wish to preserve (where applicable) theorems when reducing back to natural
>> numbers.
>
> 2 and -2 are both primes and for that reason the factorization in Z is
> only unique up to units.

Oh, and in N it isn't?

5 = 1*1*1*5. I wish to hear your arguments on which basis you have
excluded 1 from being prime. Let me remind you that 1 is the only
divisor of 1 among natural numbers. Please, avoid referring to
"this is what we were told in high (or any other) school" in your
argumentation.

> factor(6) never implemented the behavior
> descripted in the man page for possible negative numbers as the smallest
> prime factor of a number is of course the additive inverse of the
> largest (positive) prime factor and that is the last one computed. That
> is of course ignoring completely the question of why a specific
> factorization should be choosen.

Then this is what should be fixed rather than arbitrarily rejecting half
of valid inputs without any reasonable explanation behind such move.

> So this all leaves two questions:

This leaves open one question: when will you back out your changes and
leave it to others to implement correct behaviour? You don't seem to be
interested in the latter.

> (1) Should the diagnostic messages be fatal or not.  The implemented
> behavior matches the specification in the documentation in this regard,
> but for interactive use it is certainly more useful to continue reading
> numbers.

Correct implementation of factorization doesn't have to deal with this
artificial problem.

One can find parallels with the difference between elementary school and
high school which teaches that correct answer involves a set of solutions,
which may be empty or infinite.

> (2) Is printing the more convient "1: 1" more useful behavior or not. It
> is not a prime factorisation, just a product decomposition. As long as
> it is not complaimed to be something else, there is little harm in doing
> that. This is consistent with non-buggy behavior of e.g. Wolfram Alpha
> and if all you want to know are smallest factors, it is certainly a

Obviously, folks at WRI may think differently, and you didn't even consider
this possibility.

--
HE CE3OH...
```

Attachment: pgpgFyqJn7VE2.pgp
Description: PGP signature

Home | Main Index | Thread Index | Old Index