[swift-evolution] Swift 3.1 discussions, go?

[Michael Peternell]

Haha ;)

1) Maybe converting the algorithm into a tail-recursive form should be the first optimization?

func factorial(_ n: Int, multipliedBy m: Int = 1) -> Int {
    return n <= 1 ? m : factorial(n-1, multipliedBy: m*n)
}

2) Using a non-recursive algorithm would improve performance even more, I guess.

3) The third is maybe to use precalculation or an efficient algorithm that doesn't call `factorial` that often. (Assuming that your use-case isn't just calculating factorial numbers for fun.) (E.g. if you try to calculate (52 over 3) by using the formula (52!/(49!*3!)) it will be inefficient, and btw it will crash, because 52! does not fit into an Int. The efficient way is 52*51/2*50/3 ("*","/": same precedence, left-associative.)) On my 64-bit computer I cannot go beyond 20!, factorial(21) gives an EXC_BAD_INSTRUCTION a.k.a. integer overflow. There is no point in optimizing 20!, and there certainly is no point in optimizing 40!, at least with Int's.

There is really no point in optimizing that anymore beyond that. A silly SIMD-optimized algorithm is always worse than a well-designed algorithm compiled with -O0. If you do standard optimization techniques first, the advantage of SIMD-instructions for factorial become unmeasurable ;)

However, I agree that special optimizations for numeric computations (SIMD and other extension) would be cool..

-Michael

> Am 02.08.2016 um 18:37 schrieb Muse M via swift-evolution <swift-evolution at swift.org>:
> 
> I'm concern if simd could improve factorials code and faster timing.
> 
> import simd
> func factorial(n: Int) -> Int {
>     return n < 1 ? 1 : n * factorial(n: n - 1)
> }
> print(factorial(n: 40))
> 
> 
> On Wed, Aug 3, 2016 at 12:00 AM, Charlie Monroe <charlie at charliemonroe.net> wrote:
> That's a good point. :)
> 
>> On Aug 2, 2016, at 5:55 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>> 
>> I'm going to guess, since Musa mentioned science and engineering, that a good chunk of that work is floating point :)
>> 
>> 
>> On Tue, Aug 2, 2016 at 10:41 AM, Charlie Monroe via swift-evolution <swift-evolution at swift.org> wrote:
>> Are you using the variants of operators without overflow check? I.e.
>> 
>> let num = a &+ b // [1]
>> 
>> [1] https://developer.apple.com/library/ios/documentation/Swift/Conceptual/Swift_Programming_Language/AdvancedOperators.html
>> 
>> 
>> 
>>> On Aug 2, 2016, at 3:01 AM, Muse M <james.lei65 at gmail.com> wrote:
>>> 
>>> Have always wonder why Maths in Swift is slower than C and Go, it should be address with priority if Swift is to be adopt for engineering, financial and science industry.
>>> 
>>> On Tue, Aug 2, 2016 at 4:43 AM, Charlie Monroe via swift-evolution <swift-evolution at swift.org> wrote:
>>> See https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160725/025711.html
>>> 
>>> From what I understand, the discussion should stay focused on the main topics for Swift 4 that Chris highlighted in https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160725/025676.html
>>> 
>>> I had several ideas in mind, but am postponing them for Swift 5, seeing the schedule...
>>> 
>>> 
>>>> On Aug 1, 2016, at 8:48 PM, Anton Zhilin via swift-evolution <swift-evolution at swift.org> wrote:
>>>> 
>>>> It was stated that 27th of July was the last date for proposal acceptance, 29th of July was the last day for implementation, and 1th of August should be the starting day of Swift 3.1-related discussions.
>>>> Am I right? Should we begin?
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> 
>>> 
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> 
>>> 
>> 
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>> 
>> 
> 
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution