Correcting Frequency error for time keeping

Im trying to keep accurate time in my Arduino in a Mini pro.

Option 1(Preferred)

Is there a way to modify the frequency the processor believes itself to be running at in software? To try to correct error in time keeping so I don't need to use a external real-time-clock.

Basically I've calculated by running a timer over a long time they my boards all have a approximate error of: 260.60606061 ms loss per minute.. therefor I need to modify the clock speed the software believes to be running at by a factor of 0.99567534949204

Option 2

If I do need to use a RTC, I have a question about how to properly setup a Crystal oscillator. I have this crystal and matched RTC:

I just want to confirm that I would need 2 12.5pf caps for the Crystal.

Edit:
I should clarify, I'm using Time.h to keep track of time.

For anyone else having this particular issue, i found the best way to implement a time "slip"

long last_slip = 0;
void setup()   {
  last_slip = millis();
}

void loop() {
  if (0.0044 * ((millis()-last_slip)/1000) >= 1.0){// check if slip is now greater then or equal to 1s
    Serial.println("+1 s");
    adjustTime(1); // add 1s to time.
    last_slip = millis();
  }
}

0.0044 is a slip factor, I calculated the original number to be for time gain instead of loss. but this so far has kept the time to be almost perfectly in sync.

If someone else has a better option please let me know.

An RTC is one option. It has the advantage of continuing to keep time even when your processor is turned off. To select an appropriate crystal for an RTC you need to read the datasheet and any app notes for it. There are many to choose from. Some RTCs have built-in software correction, some have built-in capacitance adjustment, some have built-in factory calibrated crystals and some have automatic temperature compensation.

Another option is to replace your processor's resonator with a crystal. The error you're seeing right now is about 4000ppm. With a crystal and capacitors it would be easy to get that down to under 100ppm. And frequency variation with temperature is a lot less with a crystal.

Maybe your environment is very stable temperature-wise. I have found that the morning to night and day to day temperature variations here make it impossible to precisely software calibrate a resonator, at least without also measuring the temperature.

While perhaps not desirable for your application, it's also possible to turn your processor into a low-power RTC by replacing it's resonator with a 32.768kHz watch crystal and using the internal 8MHz oscillator for the system clock. Configured like that an Atmega328 at 3.3V draws about 1uA when simply keeping the time.

You just need to know the oscillator frequency and you get a precise second():
http://forum.arduino.cc/index.php?topic=183056.0

It can't be any more precise than the oscillator itself. I just turned on my Uno about 10 minutes ago. Here's how much the resonator varied in that short time:

15983237 Hz, -1048 ppm
15982648 Hz, -1085 ppm

That's a difference that would equal about 3 seconds per day. Over the course of a typical day (indoors) the frequency might vary by around 150ppm, about 13 sec/day. Now maybe that's good enough or maybe it's not. It depends.

A crystal is a huge improvement. In the same 10 minutes a crystal I was measuring didn't vary at all (to a resolution of 1 ppm). In a typical day it might only change by 2-3 ppm.

However editing wiring.c presents a different problem. Unless you have only one processor that you compile for you will have to edit this core file to change it whenever you compile for a different one. It would be better to have some sort of callback function or... I don't know. Something you could do at the sketch level.

edit: Maybe this is an appropriate situation for using the method described in post #7 of this thread.