digitalBush

Yesterday I posted an Oracle SQL query that would produce primes, but it wasn't an implementation of the Sieve of Eratosthenes. Here for your viewing pleasure discomfort is a version in Oracle PL/SQL.

create or replace package josh.sieve as
   type prime_numbers is table of number;
   function calculate ( the_end number ) return prime_numbers pipelined;
end;
/

create or replace package body josh.sieve as
   function calculate ( the_end number ) return prime_numbers pipelined is
      type bitbucket is table of boolean index by binary_integer;
      primes bitbucket;
      max_sqrt number :=floor(sqrt(the_end));
      i number:=3;
      j number:=1;
    begin
        pipe row(2);

        for i IN 1 .. the_end loop
          primes(i) := true;
        end loop;

        while i <= the_end loop
          if primes(i) then
            if(i<=max_sqrt) then
              j:=i*i;
              while j<=the_end loop
                primes(j):=false;
                j:=j+2*i;
              end loop;
            end if;

            pipe row(i);
          end if;

          i:=i+2;
        end loop;
    end;
end;
/

This is the ugliest one so far. It really burns my eyes!

What I liked
I was kind of pleased to see the pipe row(foo); functionality. This is very similar to yield in c# where I can just lazily return numbers as they are found instead of building up the whole list table in advance.

What I hated
There's a bunch here. First off, I tried to write this with a for loop, but there is no way to define the step value. I had to resort to using a while loop with an external counter variable. It also sucks that I have to define a custom type which is just a table of numbers. Finally, I didn't see a clean way to initialize a table with a size and default value.

Why it burns my eyes
I'm not digging that assignments have to have a colon-equal "foo := 42" operator. To the same tune as basic, I hate that blocks end with an end keyword. This is an especially big WTF when you consider that lines are terminated with semi-colons. The end result is a bunch of colon-ish punctuation littered with end keywords.

Regardless, I was pleased with the performance. Running a query like select count(1) from table(josh.sieve.calculate(1000000)); runs in about 600 milliseconds on our db machine. Not too shabby...

I just want to throw this out there since it's useful. I searched and didn't come up with an Oracle specific implementation of this algorithm, so here it is. This function checks if a given National Provider Identifier(NPI) is valid. The Luhn Algorithm is used to validate NPI after a prefix of "80840" is applied.

This code is provided as is. I'm not making any guarantees that it's 100% right and I'm not responsible if anything bad happens as a result of your use of this. So, don't yell at me if small animals are harmed with the use of this code.

--Returns 1 if valid, 0 if invalid
CREATE OR REPLACE FUNCTION valid_npi (npi in varchar)
RETURN number
IS
    tot NUMBER := 24; --80840 prefix for npi
    val NUMBER := 0;
BEGIN
  if(
    npi is null or
    length(npi) <> 10 or
    LENGTH(TRIM(TRANSLATE(npi, '0123456789', ' ')))>0 --not numeric
  ) then
    return 0;
  end if;

  for i IN reverse 1 .. LENGTH(npi) loop
    val:=SUBSTR(npi, i, 1);
    if mod(i,2)=1 then
      val := val * 2;
      if(val > 9) then
        val:=val-9;
      end if;
    end if;

    tot := tot + val;
  end loop;

  if(MOD(tot, 10)=0) then
    return 1;
  else
    return 0;
  end if;
END valid_npi;