Click here to Skip to main content
Click here to Skip to main content
Alternative Tip/Trick

Tagged as

Legendre Symbol (C# code)

, 24 Apr 2012 CPOL
Rate this:
Please Sign up or sign in to vote.
This is an alternative for "Legendre Symbol (C# code)"

Introduction

This is an alternative to the original Legendre Symbol (C# code)[^]. That implementation suffered from a simple, but significant, error, and significant inefficiency.

Background

See the Wikipedia article "Legendre symbol"[^] for the definition and theory behind this.

Using the code

Here is my implementation of the method:

    public static int Legendre(int a, int p)
    {
      if (p < 2)  // prime test is expensive.
        throw new ArgumentOutOfRangeException("p", "p must not be < 2");
      if (a == 0)
      {
        return 0;
      }
      if (a == 1)
      {
        return 1;
      }
      int result;
      if (a % 2 == 0)
      {
        result = Legendre(a / 2, p);
        if (((p * p - 1) & 8) != 0) // instead of dividing by 8, shift the mask bit
        {
          result = -result;
        }
      }
      else
      {
        result = Legendre(p % a, a);
        if (((a - 1) * (p - 1) & 4) != 0) // instead of dividing by 4, shift the mask bit
        {
          result = -result;
        }
      }
      return result;
    }

Compared to the original this has added:

  • static declaration because it is self-contained (doesn't depend on any class instance values)
  • initial "validation" of p
  • correct checking for a == 0 (Without it, infinite recursion was possible. Try L(3,3).)

Most significantly, the computationally expensive use of Math.Pow() to set the sign of the result has been replaced with all integer operations. This implementation is about 7 times faster than the original tip.

The attached zip file has both implementations, with code for timing and verification of identical results on about 16 million test cases.

Points of Interest

In the original sign manpulation code -1 was being raised to an integer power to be either +1 or -1, and then multiplied by the recursion result to conditionally change the sign of that result. It is only necessary to change the sign if that integer power is odd so a lowest-order bit test will do the job. Since in the original sign manipulation code cases the factors were divided by 8 or 4 (both powers of 2) before being used, the equivalent to the division-then-bit-test is just to shift the bit being tested and avoid the division entirely.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Matt T Heffron
Software Developer (Senior) AB Sciex
United States United States
I started programming in Basic on a DECSystem-10 as a Freshman at Caltech in 1974. I quickly transitioned to assembly language, Fortran, and Pascal. As a summer job at JPL, I did analysis of fuel consumption for the Viking Mars Orbiter attitude control system. I also spent a summer doing O/S maintenance at Digital Equipment Corporation.
After graduation, I started developing microprocessor development tools (e.g., cross-compiler, debugger) for Beckman Instruments, a scientific instrument company.
I've worked on custom file-systems, a real-time O/S for Z8000, Expert Systems (SpinPro & PepPro), and internal and external networking support (I was their first webmaster).
I've worked on the DNA analysis system.
I was the console/UI software architect for Ultracentrifuges and protein Capillary Electrophoresis systems.
After 35 years, Danaher having acquired Beckman (now Beckman Coulter), transferred the CE group to become part of AB Sciex (2014).

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141223.1 | Last Updated 24 Apr 2012
Article Copyright 2012 by Matt T Heffron
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid