# Typeof(n\*n) in factorial

**URL:** <https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700>\
**Category:** Internals & Design\
**Created:** [June 18, 2020, 9:45pm UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700 "2020-06-18T21:45:45Z")\
**Posts on this page:** 10\
**Page:** 2

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [June 19, 2020, 12:54pm UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/21 "2020-06-19T12:54:13Z")

</div>

I can be wrong but to me it seems like a performance improvement. If the bindings in both sides of `*=` are `typeassert`ed to the same type, then no conversions or type instability happens.

However, it seems like it can affect the correctness of the algorithm. If `*` can return a type different of both operands (and it can, as this is the whole reason for using `typeof(n*n)` instead of `typeof(n)`), then there is no guarantee that `f * i` will return `typeof(n*n)`, there can be that `typeof((n*n)*(n*n))` is a different type, in this case declaring a type for the variable make the algorithm try to convert the new type back to the old type, and if the new type does not fit the old type, what is very probably the reason because it is different, then an `InexactError` will probably be raised.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [June 19, 2020, 2:39pm UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/22 "2020-06-19T14:39:30Z")

</div>

> [@karlroyen](#):
>
> `n*n` is not closed under multiplication, why should `(n*n)*n` be?

I think the reason for n\*n might be related to Int64 always returned:

```julia
julia> factorial(Int32(10))
3628800

julia> typeof(ans)
Int64

julia> typeof(ans) # unlike for Int32(10)*Int32(10); @code_native UInt32(10)*UInt32(10) gives different instruction than for 10*10, and on some CPUs/platforms faster (only 32-bit ones?)

Int64

```

I was tuning this code (successfully, but didn’t get merged), and it’s a bit ugly as intentionally it returns Int64 (also on 32-bit platforms, still type-stable on both).

I do not recall, and didn’t have 32-bit Julia to test, but I know 32-bit assembly multiply is faster than for 64-bit (I’m not sure it’s much faster but I was going to exploit this in another context), so that’s one reason for n\*n to return a wider type 64-bit, while if I would again multiply it with 32-bit or 64-bit I wouldn’t go wider still, as then there’s no fast multiply (you can stil lwork with Int128, it’s just slower).

[32-bit seems like a happy medium for me in a lot of contexts, such as array indexes, not base pointers, and then if I widen to 64-bit on multiply, I get space saving without overflow of multiply, getting best of both 32- and 64-bit.]

> [@Tamas\_Papp](#):
>
> `Int` & friends use lookup tables, `BigInt` [falls back to using `MPZ`](https://github.com/JuliaLang/julia/blob/d6d5208d66be637543232bec4b0c79b2811ea1c6/base/gmp.jl#L641).

With my optimization, I was changing that, because lookup-tables are surprisingly slow (unlike in the old days, when a useful optimization trick). I.e. I was changing for Int (but also BigInt, I was less concerned with speeding that up, as I’m not sure how much used in practice, but a fallback to my Int code, and maybe a lookup for low values might help).

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 20, 2020, 7:30am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/23 "2020-06-20T07:30:35Z")

</div>

> [@Palli](#):
>
> I think the reason for n\*n might be related to Int64 always returned

But that’s an [explicit conversion](https://github.com/JuliaLang/julia/blob/35c1f87176fecab5a8e8077fb3a62275363a5aa5/base/combinatorics.jl#L33) and has nothing to do with the method above.

The only thing I could find that calls that method is `factorial(true)`.

I think that the bottom line is that while `Base` has a lot of high-quality code, it also has stuff that’s there for no apparent reason (or maybe there was a good reason originally, but things moved on).

This particular code will probably be changed when someone refactors it for some other reason unrelated to this, since for most numerical types,

```julia
typeof(n * n) === typeof(n)

```

so it is innocuous.

Incidentally, I wish people wrote more comments with code.

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [June 20, 2020, 9:30am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/24 "2020-06-20T09:30:34Z")

</div>

One could specify that user-defined types should provide a method for `Base.to_power_type` unless the fallback already works. Then implement `factorial` using that. Something like:

```julia
function factorial(n::Integer)
    n < 0 && throw(DomainError(n, "`n` must be nonnegative."))
    i = to_power_type(n)
    f = one(i)
    while i > one(i)
        f *= i
        i -= one(i)
    end
    return f
end

```

Still, I’m quite happy with the current implementation. It works out of the box with StaticNumbers, and that would not be the case if it had used `typeof(n)` as the output type.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 20, 2020, 10:01am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/25 "2020-06-20T10:01:38Z")

</div>

I disagree with this — unless someone demonstrates a use case/exception, types that we think of as “numbers” should just be closed under `*`.

As mentioned above, there are types for which this does not hold, but for those `factorial` makes little sense anyway.

If we really want to formalize it, I would go with a trait that tells whether a type is closed under `*`. But that may be overkill.

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [June 20, 2020, 11:00am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/26 "2020-06-20T11:00:21Z")

</div>

have a look at `Base.power_by_squaring` it already uses

```julia
to_power_type(x) = convert(Base._return_type(*, Tuple{typeof(x), typeof(x)}), x)

```

@Tamas_Papp: An example that comes to my mind is with symbolic tools: an expression can be written efficiently (in a particular representation), but it’s square (or nth power) can’t and then you may wish to change into generic implementation.

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [June 20, 2020, 11:02am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/27 "2020-06-20T11:02:09Z")

</div>

> [@Tamas\_Papp](#):
>
> types that we think of as “numbers” should just be closed under `*`

By that standard, `Base.Irrational` doesn’t qualify…

I think StaticNumbers is a good example of Number types that are useful but not closed under multiplication. Although they are mostly intended for things like passing the sizes of NTuples and StaticArrays in a type-stable way, they are also meant to work with general math, and usually lead to efficient constant-folding. For example:

```julia
julia> @code_llvm factorial(static(20))

; @ intfuncs.jl:889 within `factorial'
define i64 @julia_factorial_7662() {
top:
; @ intfuncs.jl:895 within `factorial'
  ret i64 2432902008176640000
}

```

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 20, 2020, 11:30am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/28 "2020-06-20T11:30:48Z")

</div>

> [@Per](#):
>
> > [@Tamas\_Papp](#):
> >
> > types that we think of as “numbers” should just be closed under `*`
> 
> By that standard, `Base.Irrational` doesn’t qualify…

Precisely — that’s why I used “numbers” instead of `<:Number`.

It would be great to be able to have traits that determine if a type is

1. closed under `+`, `-`, and `*` (more or less a [ring](https://en.wikipedia.org/wiki/Ring_(mathematics)))
2. closed under that and `/` (a [field](https://en.wikipedia.org/wiki/Field_(mathematics))),
3. closed under transcendental functions etc

with alternative functions that just give a type that can contain the result for each of the above, eg

```julia
transcendental_result_type(::Type{Irrational{T}}) where T = Float64

```

Much more fine-grained descriptions would be possible, and also a complete set of shadow operators over types (eg `Int/Int === Float64`, what is currently done with return types), but overcomplicating this may be too much at this point, the caller should just `promote` and arrive quickly at a concrete type that can contain the result, or fall back to `Any`.

I tried to do part of this in

> **[GitHub - tpapp/AlgebraResultTypes.jl: result type calculations for algebraic...](https://github.com/tpapp/AlgebraResultTypes.jl)**
>
> result type calculations for algebraic operations. Contribute to tpapp/AlgebraResultTypes.jl development by creating an account on GitHub.

in a more complicated way, but that does not scale.

---

<div class="post-metadata">

**Author:** ![Per](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/per/32/10387_2.png) [@Per](https://discourse.julialang.org/u/Per)\
**Post date:** [June 20, 2020, 11:57am UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/29 "2020-06-20T11:57:46Z")

</div>

That package looks really useful! All that is needed is than anyone who creates a number type for which the default `result_ring` or `result_field` don’t give the right result add their own methods.

(It might also be nice to have `of_ring_type(x)` as a shorthand for `result_ring(typeof(x))(x)`.)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 20, 2020, 12:01pm UTC](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700/30 "2020-06-20T12:01:29Z")

</div>

Thanks, but I am now considering revamping this. TL;DR:

```julia
result_field(T, S)

```

is probably not needed as often as

```julia
result_field(promote_type(T, S))

```

so simple functions that map from types to types should be sufficient for 99% of the cases and would allow much simpler code.

[Previous page](https://discourse.julialang.org/t/typeof-n-n-in-factorial/41700.md?page=1)