On Tuesday, 19 March 2013 at 15:55:19 UTC, ixid wrote:
> I was just looking at the Rosetta code for prime decomposition and it seems bugged to me, wanted to make sure as you seem to be the one coordinating these things:
>
> http://rosettacode.org/wiki/Prime_decomposition#D
>
> This will potentially return a 1 in the list of primes which is a bug as 1 isn't prime.

You're right. I think the right code for decompose is this:

T[] decompose(T)(T n) /*pure nothrow*/ {
	T[] res;
	for (T i = 2; n % i == 0;) {
		res ~= i;
		n /= i;
	}
	for (T i = 3; n != 1; i += 2) { // ----- Changed condition
		while (n % i == 0) {
			res ~= i;
			n /= i;
		}
	}
        // ----- Removed concat here
	return res;
}

ixid:

> http://rosettacode.org/wiki/Prime_decomposition#D
>
> This will potentially return a 1 in the list of primes which is a bug as 1 isn't prime.

From Python code, hopefully more correct and much faster:

http://codepad.org/N4A7kxE1

Bye,
bearophile

On Tuesday, 19 March 2013 at 16:47:43 UTC, Andrea Fontana wrote:
>
> On Tuesday, 19 March 2013 at 15:55:19 UTC, ixid wrote:
>> I was just looking at the Rosetta code for prime decomposition and it seems bugged to me, wanted to make sure as you seem to be the one coordinating these things:
>>
>> http://rosettacode.org/wiki/Prime_decomposition#D
>>
>> This will potentially return a 1 in the list of primes which is a bug as 1 isn't prime.
>
> You're right. I think the right code for decompose is this:
>
> T[] decompose(T)(T n) /*pure nothrow*/ {
> 	T[] res;
> 	for (T i = 2; n % i == 0;) {
> 		res ~= i;
> 		n /= i;
> 	}
> 	for (T i = 3; n != 1; i += 2) { // ----- Changed condition
> 		while (n % i == 0) {
> 			res ~= i;
> 			n /= i;
> 		}
> 	}
>         // ----- Removed concat here
> 	return res;
> }

T[] primeDecomposition2(T)(T n) /*pure nothrow*/ {
    T[] res;
    for (T i = 2; n % i == 0;) {
        res ~= i;
        n /= i;
    }
    for (T i = 3; n >= i * i; i += 2) {
        while (n % i == 0) {
            res ~= i;
            n /= i;
        }
    }

	if(n != 1)
		res ~= n;

    return res;
}

I think this is quite a lot faster, otherwise for numbers that are the products of a small and larger prime it will waste a lot of time reaching the larger prime's value.

On Tuesday, 19 March 2013 at 17:18:01 UTC, bearophile wrote:
> ixid:
>
>> http://rosettacode.org/wiki/Prime_decomposition#D
>>
>> This will potentially return a 1 in the list of primes which is a bug as 1 isn't prime.
>
> From Python code, hopefully more correct and much faster:
>
> http://codepad.org/N4A7kxE1
>
> Bye,
> bearophile

This method seems to be a lot slower than just adding an if
statement while giving the same answers (after sorting). For me
it took 1.5 seconds to decompose 2 to 100,000 compared to 150ms
for the method I posted above. Can you find an error in my method
or shall I post that? I'll add a cast(T) 1 to the if statement so
it can deal with big ints too.

ixid:

> Can you find an error in my method or shall I post that?

Small changes on your version:
http://codepad.org/E9KHKvAi


> I'll add a cast(T) 1 to the if statement so
> it can deal with big ints too.

There's no need for that.

Bye,
bearophile

> Small changes on your version:
> http://codepad.org/E9KHKvAi

It's now on Rosettacode. I have added more changes to make it able to deal with immutable input.

Bye,
bearophile

On Tuesday, 19 March 2013 at 18:53:21 UTC, bearophile wrote:
>> Small changes on your version:
>> http://codepad.org/E9KHKvAi
>
> It's now on Rosettacode. I have added more changes to make it able to deal with immutable input.
>
> Bye,
> bearophile

Another issue to consider as the question I was attempting ended up requiring this, I wasn't aware of it when I made the original post:

The prime factorization of 1 is an empty set, so surely to be correct it should return [] when given 1 and not throw an exception. This also suggests a possible modification to [].reduce!"a * b" as mathematically the product of the empty set is defined as 1.

ixid:

> The prime factorization of 1 is an empty set, so surely to be correct it should return [] when given 1 and not throw an exception.

The Task says that the input can't be 1, so the input 1 needs to be a pre-condition violation:

>Write a function which returns an array or collection which contains the prime decomposition of a given number, n, greater than 1<


> This also suggests a possible modification to [].reduce!"a * b" as mathematically the product of the empty set is defined as 1.

reduce() is a general function, so it's not supposed to know that.

Python reduce does the same:


>>> reduce(lambda a, b: a * b, [])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: reduce() of empty sequence with no initial value


If you want that, then you have to use:
reduce!"a * b"(1, items)

And some time from now:
items.reduce!"a * b"(1)


If we add a product() function to Phobos similar to sum() (http://d.puremagic.com/issues/show_bug.cgi?id=4725 ) then I agree that for empty ranges it will need to return the multiplicative identity element.

Bye,
bearophile

Some comments about the recently created "Vampire number" task in Rosettacode:

The version I have modified:
http://rosettacode.org/mw/index.php?title=Vampire_number&diff=154069&oldid=154068


Fwend has reverted most of my changes:
http://rosettacode.org/wiki/Vampire_number#D

------------

The rationale for some of my changes:

- main at the bottom. Giving a predicable order to the parts of the program is good. This how all the other entries are made.
- Removal of "if (auto factors = ...)": coding standards suggest to avoid mixing conditional tests with actions. Keeping code more tidy is safer.
- Removal of complex for loops "for (long n, count; n < long.max && count < 25; n++)": it's better to keep the loop semantics simpler. It's better for both the optimization and for the readability and keeping the code in time.
- Adding immutable/const to the foreach loop variable "foreach (n; [...])": D currently gives a warning if you try to mutate it. In future D will allow you to mutate it, but it's only a copy, as in Python. This is potentially confusion. Marking it as const/immutable should become a standard D coding convention to avoid troubles. It's not useless.
- "immutable q = k / i;" instead of "long q = k / i;" all variables in a D program that don't need to mutate should be annotated with const/immutable. This gives more optimization to the compiler, helps avoid bugs of unwanted mutation later, and makes code simpler to understand, because when you read code you are sure something is not changing. It's explained here, among other places: http://blog.knatten.org/2011/11/11/disempower-every-variable/
- "if (digits.length % 2)" instead of "if (digits.length & 1)": for the compiler they are exactly the same, because the value is unsigned. And using a modulus is more clear here. We are discussing about parity, not about bits.
- "immutable f1 = getDigits(pair[0]);" instead of "auto f1 = getDigits(pair[0]);": as before, f1 doesn't need to change, so it should be immutable (I have used const, but immutable is better, because getDigits is now pure).
- Annotations like "pairs ~= [i, q]; // Heap-allocated pair.": they are useful because that little 2 items array is allocated on the heap. It's good to remember us an important inefficiency in the code. If you use a 2-tuple such inefficiency vanishes. Someday hopefully this significant inefficiency of array literals will be removed, and the comment will be removed.
- "// Unnecessary cast. Array concat allocates a new array." + "if (!(cast(long[])(f1 ~ f2)).sort().equal(digits))" instead of " if(!equal(digits, (f1 ~ f2).sort()))": f1 and f2 are immutable, and currently if you concatenate them you get an immutable array, that you can't sort. I agree the cast is bad here, so I have to use dup instead. In future this problem will be hopefully removed, so the code will be fixed and the comment removed. RosettaCode is not just a show of D code, it's also a place to help us improve D language itself. So hundreds of D entries in Rosettacode have annotations like that, that help us remember limits or bugs or problems in the D language. I have removed tens of similar annotations when D bugs get fixed. They are useful for the development od D.


(Here I have listed only the things that I think should be reverted. There are other things in my version of the problem that are more like personal style preferences that I have not listed here, that are used in most or all the other D entries.)

Bye,
bearophile

> - Removal of "if (auto factors = ...)": coding standards suggest to avoid mixing conditional tests with actions. Keeping code more tidy is safer.

Also in D testing array emptiness like that is generally dangerous. The idiomatic and correct way to do it in D is to use empty. Because in general arrays with zero length can be true:

Another thing: the problem asks to return the results for 16758243290880, 24959017348650, 14593825548650, while your version of the program doesn't even show the last numbers. This is bad. The Python entry shows all three of them.

Bye,
bearophile