F# Power issues which accepts both arguments to be bigints

Question

I am currently experimenting with F#. The articles found on the internet are helpful, but as a C# programmer, I sometimes run into situations where I thought my solution would help, but it did not or just partially helped.

So my lack of knowledge of F# (and most likely, how the compiler works) is probably the reason why I am totally flabbergasted sometimes.

For example, I wrote a C# program to determine perfect numbers. It uses the known form of Euclids proof, that a perfect number can be formed from a Mersenne Prime 2p−1(2p−1) (where 2p-1 is a prime, and p is denoted as the power of).

Since the help of F# states that '**' can be used to calculate a power, but uses floating points, I tried to create a simple function with a bitshift operator (<<<) (note that I've edit this code for pointing out the need):

 let PowBitShift (y:int32) = 1 <<< y;;

However, when running a test, and looking for performance improvements, I also tried a form which I remember from using Miranda (a functional programming language also), which uses recursion and a pattern matcher to calculate the power. The main benefit is that I can use the variable y as a 64-bit Integer, which is not possible with the standard bitshift operator.

    let rec Pow (x : int64) (y : int64) = 
    match y with
        | 0L -> 1L
        | y -> x * Pow x (y - 1L);;

It turns out that this function is actually faster, but I cannot (yet) understand the reason why. Perhaps it is a less intellectual question, but I am still curious.

The seconds question then would be, that when calculating perfect numbers, you run into the fact that the int64 cannot display the big numbers crossing after finding the 9th perfectnumber (which is formed from the power of 31). I am trying to find out if you can use the BigInteger object (or bigint type) then, but here my knowledge of F# is blocking me a bit. Is it possible to create a powerfunction which accepts both arguments to be bigints?

I currently have this:

let rec PowBigInt (x : bigint) (y : bigint) = 
    match y with
        | bigint.Zero -> 1I
        | y -> x * Pow x (y - 1I);;

But it throws an error that bigint.Zero is not defined. So I am doing something wrong there as well. 0I is not accepted as a replacement, since it gives this error:

Non-primitive numeric literal constants cannot be used in pattern matches because they    
can be mapped to multiple different types through the use of a NumericLiteral module.  
Consider using replacing with a variable, and use 'when <variable> = <constant>' at the 
end of the match clause.    

But a pattern matcher cannot use a 'when' statement. Is there another solution to do this?

Thanks in advance, and please forgive my long post. I am only trying to express my 'challenges' as clear as I can.

Laborsaving

Nice first question, welcome to Stack Overflow! – Tripetalous

Answer 1

I failed to understand why you need y to be an int64 or a bigint. According to this link, the biggest known Mersenne number is the one with p = 43112609, where p is indeed inside the range of int.

Having y as an integer, you can use the standard operator pown : ^T -> int -> ^T instead because:

let Pow (x : int64) y = pown x y
let PowBigInt (x: bigint) y = pown x y

Regarding your question of pattern matching bigint, the error message indicates quite clearly that you can use pattern matching via when guards:

let rec PowBigInt x y = 
    match y with
    | _ when y = 0I -> 1I
    | _ -> x * PowBigInt x (y - 1I)

Presently

Ah, that is quite clearifying, I did not yet understand that you can preceed an underscore within a pattern matcher. Regarding the need of a bigint, I am writing a program which can display the 10th (and above) perfect number, which in fact cannot be placed inside a 64bit integer (or a long as some prefer). – Laborsaving

You misunderstood something. 2^p-1 should be bigint, but int for p is more than enough. So the parameter y need not to be int64 or bigint. It's the same reason why pown has the second parameter as an int. – Presently

That is indeed correct, how silly of me. However the 47th perfect number has a power of 43.112.609, and it is not yet known what the next power will be. This I have found on: en.wikipedia.org/wiki/List_of_perfect_numbers My goal is writing a program which at least can do an attempt to find all 47 perfect numbers (and hopefully more, but that might be an exhaustive attempt). – Laborsaving

@Laborsaving - hopefully more indeed! – Orchardist

@Stephen Swensen indeed, I knew I recognized your name, now I know. You have that blog about Project Euler! One of the sites that triggered me into this matter. For that I thank you :-) (However, my wife will probably think different, seeing the amount of time I am spending on my PC...) Just out of curiosity, have you tried to achieve this as well? – Laborsaving

@Laborsaving - Wow, I had no idea anyone actual read my Project Euler blog! That's really neat to hear, maybe it will make my wife happier to know that all the time I spent on it was worth it to someone other than me :) I don't recall working on even perfect numbers specifically, but I have spent an unusual amount of time in the past trying to prove that there are no odd perfect numbers (or alternatively that there are infinitely many!), and one of my first bits of F# code was implementing the sigma function. – Orchardist

Very interesting comments. I wish I had a wife and a blog to talk about :D. – Presently

@StephenSwensen you have no idea on how long I have been reading and studying your blog ;-). I can only hope that one day I might have learned just a fraction of the knowledge and skills you have. Your efforts are definitely worth it, perhaps more people have read your blog, but as with many articles and blogs on the Internet, just a few place their comments or grattitude (like myself to be honest). So please continue, it really helps! – Laborsaving

@pad, thank you, but you also got this started of course! Right now, my small program is able to find the 10th perfect number within 54 seconds (and displaying the 9 before them). The 11th number will take more time, so I will need to think of a way to let my cores calculate parallel. Studying the link on: msdn.microsoft.com/en-us/library/dd460693.aspx will help me understanding how parallel programming works. The last time I programmed something parallel was somewhere in 2001, using OCCAM. I don't even know if that language has evolved or not. So thank you all!! – Laborsaving

Answer 2

I think the easiest way to define PowBigInt is to use if instead of pattern matching:

let rec PowBigInt (x : bigint) (y : bigint) =  
  if y = 0I then 1I   
  else x * PowBigInt x (y - 1I) 

The problem is that bigint.Zero is a static property that returns the value, but patterns can only contain (constant) literals or F# active patterns. They can't directly contain property (or other) calls. However, you can write additional constraints in where clause if you still prefer match:

let rec PowBigInt (x : bigint) (y : bigint) =  
  match y with 
  | y when y = bigint.Zero -> 1I 
  | y -> x * PowBigInt x (y - 1I)

As a side-note, you can probably make the function more efficent using tail-recursion (the idea is that if a function makes recursive call as the last thing, then it can be compiled more efficiently):

let PowBigInt (x : bigint) (y : bigint) =   
  // Recursive helper function that stores the result calculated so far
  // in 'acc' and recursively loops until 'y = 0I'
  let rec PowBigIntHelper (y : bigint) (acc : bigint) =
    if y = 0I then acc 
    else PowBigIntHelper (y - 1I) (x * acc)
  // Start with the given value of 'y' and '1I' as the result so far
  PowBigIntHelper y 1I

Regarding the PowBitShift function - I'm not sure why it is slower, but it definitely doesn't do what you need. Using bit shifting to implement power only works when the base is 2.

Neediness

Well I need to rephrase my question a bit, the code I placed is not correct, since the calculation needs a power of two, I thought that a shift to the left (the exponent part) on 1 (one as a base) would do the trick. In my code the x is filled with value one, which could be replaced by the constant value itself off course. I will have to do another test to look if it is faster or not. Thank you for your extensive answer Thomas, I will try things out. Your answer led my thought to find a smaller mistake, which I will also try to fix. – Laborsaving

Answer 3

You don't need to create the Pow function. The (**) operator has an overload for bigint -> int -> bigint. Only the second parameter should be an integer, but I don't think that's a problem for your case. Just try

bigint 10 ** 32 ;;

val it : System.Numerics.BigInteger =
  100000000000000000000000000000000 {IsEven = true;
                                     IsOne = false;
                                     IsPowerOfTwo = false;
                                     IsZero = false;
                                     Sign = 1;}

Communal

Answer 4

Another option is to inline your function so it works with all numeric types (that support the required operators: (*), (-), get_One, and get_Zero).

let rec inline PowBigInt (x:^a) (y:^a) : ^a =  
  let zero = LanguagePrimitives.GenericZero 
  let one = LanguagePrimitives.GenericOne
  if y = zero then one
  else x * PowBigInt x (y - one) 

let x = PowBigInt 10 32     //int
let y = PowBigInt 10I 32I   //bigint
let z = PowBigInt 10.0 32.0 //float

I'd probably recommend making it tail-recursive, as Tomas suggested.

Winchester

Excuse me for not leaving a comment Daniel, I simply missed your reaction. Tail recursion caught my interest, but your example here helped me to understand the language F# more and more. The more I learn from all of you, the more enthusiastic I become! Anyway, thank you very much for your efforts Daniel, it is very much appreciated! – Laborsaving