Show Posts
Pages: 1 ... 7 8 [9] 10 11 ... 25
121  Community / Exhibition / Gallery / Re: Arduino generating prime numbers on: November 05, 2013, 01:14:09 pm
Got a speed improvement of an average factor of about 2.3 over the Nick's BigNumber-based code shown in reply #43, starting at 1000000000000001, 16 digits, by making these changes:
  • Added a trial division test using byte-sized primes, before other testing.
  • Modified the Miller-Rabin test to use 2, 3, 5, 7, 11, 13, 17, 19, and 23, rather than random numbers.  This Wikipedia link - http://en.wikipedia.org/wiki/Strong_pseudoprime#Examples - says that there's no number less than 3825123056546413051, 19 digits, about 1.6 x 261, that will fool every single-pass Miller-Rabin tests with these bases.
  • [Edit: Add this] Modified loop parameters to wield only integers = 6k + 1 and 6k - 1, for integer k.

Most of the speed improvement appears to come from eliminating Miller-Rabin tests for numbers that divide by small primes.  That suggests that there may be a sweet spot for the number of prime divisors in the trial division test that depends on the speed of the Miller-Rabin test, and it may be different from the one I chose.  Lesser improvement comes from eliminating selection of random BigNumbers, and reducing the number of Miller-Rabin tests from ten to nine.  [Edit: Add this] The 6K +- 1 trick doesn't do much, since it only eliminates multiples of 3, and those fail the trial division test almost immediately.

Average displayed time was about 11.5 mS for the primes shown in replies #44 and #45.   It also ran about 3.5% slower than the values shown in reply #64 - calculation times were sometimes wildly different, but on average, they were almost as good.

Here's the code, based on the sketch in reply #43, minimally changed, auto-formatted:
Code:
#include <BigNumber.h>
PROGMEM prog_uchar primes[] = {
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31,
  37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
  83, 89, 97,101,103,107,109,113,127,131,137,
  139,149,151,157,163,167,173,179,181,191,193,
  197,199,211,223,227,229,233,239,241,251
};
const byte nPrimes = sizeof(primes)/sizeof(primes[0]);

const char FIRST_PRIME_TO_USE [] =  "1000000000000001";

BigNumber candidate;
BigNumber one (1);
BigNumber two (2);

byte bump = 2;

void setup()
{
  BigNumber five (5);
  BigNumber six (6);

  Serial.begin(115200);
  while (!Serial) {
  }

  BigNumber::begin ();  

  Serial.println ();
  Serial.println ();
  Serial.println ("Starting.");

  candidate = BigNumber (FIRST_PRIME_TO_USE);

  BigNumber rem = candidate % six;
  while ((rem != one) && (rem != five)) {
    rem = rem + one;
    rem = rem % six;
    candidate = candidate + one;
  }
  if (rem == one) {
    bump = 4;
  }
}  // end of setup

void loop()
{

  for ( ; candidate < BigNumber ("9999999999999999"); candidate += bump, bump = 6 - bump)
    showIfPrime (candidate);

  candidate = 3;  // back to start!
}  // end of loop

void rng (BigNumber & result)
{
  result = BigNumber (random ());  
}  // end of rng

bool Miller(BigNumber source)
{

  if(source == 2 || source == 3)
    return true;
  if(source < two || source % two == 0)
    return false;

  BigNumber d = source - one;
  int s = 0;

  while(d % two == 0)
  {
    d /= two;
    s += one;
  }

  const byte bases[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
  const byte nbases = sizeof(bases)/sizeof(bases[0]);
  for(int i = 0; i < nbases; i++)
  {
    //    do
    //    {
    //      rng (a);
    //    }
    //    while(a < two || a >= source - two);

    BigNumber a = BigNumber (bases[i]);
    BigNumber x = a.powMod (d, source);
    if(x == one || x == source - one)
      continue;

    for(int r = 1; r < s; r++)
    {
      x = x.powMod(two, source);
      if(x == one)
        return false;
      if(x == source - one)
        break;
    }

    if(x != source - one)
      return false;
  }

  return true;
}  // end of Miller

const byte DIGITS = 16;

unsigned long start;
unsigned long lastShown;
long found = 1; // Number we found

void showIfPrime (BigNumber num)
{
  if (!check(num))
    return;
  if (!Miller (num))
    return;

  char buf [20] = { 0 };
  long long temp = num;
  byte pos = 0;

  // make printable
  for (pos = 0; pos < DIGITS; pos++)
  {
    if (temp == 0)
      break;
    char digit = temp % 10;
    buf [DIGITS - 1 - pos] = digit | '0';
    temp /= 10;
  }

  // insert leading spaces
  for (; pos < DIGITS; pos++)
    buf [DIGITS - 1 - pos] = ' '; //  = 15;


  Serial.print(num);
  Serial.print(" is prime. Took ");
  Serial.print(millis () - start);
  Serial.print (" mS. Found ");
  Serial.print (found);
  Serial.println (" primes.");
  start = millis ();

  found++;

  lastShown = millis ();

}  // end of showIfPrime

bool check(BigNumber n) {
  for (byte i = 0;i < nPrimes; i++) {
    BigNumber f = BigNumber(pgm_read_byte_near(primes + i));
    if ((n % f) == 0) {
      return false;
    }
  }
  return true;
}
122  Using Arduino / Audio / Re: Amplified Signal to Arduino Mega on: October 31, 2013, 09:01:37 pm
This gizmo claims that it can operate as a limiter, and accommodate 60 dB on its inputs with only about 0.5 dB change on the outputs. 

http://www.onsemi.com//pub/Collateral/SA575-D.PDF

It's available in a through-hole mount for something around $5.50 from Mouser, though the through-hole version is marked "end-of-life."  If that's true, you should be able to get the a flat output response over a voltage input range of 1000.  Using the "+10 dB ~ twice as loud" rule of thumb, that's an apparent loudness range factor of 64.  That might do it.
123  Using Arduino / Programming Questions / Re: kurtosis calculations on an analog signal on: October 29, 2013, 07:32:50 pm
Every time loop() executes, the counter variable - i - is incremented, whether it's time to take a sample or not.  loop() executes many times between samples, so the counter reaches its limit quite quickly, and the output data prints.

Since the counter is supposed to be counting samples, it needs to be incremented only when a sample is taken.  It needs to be inside the brackets of the "if (currentMillis ... " test.

[Edit: Add this]  After a closer look:
  • Proper indentation will make your code easier to read and understand, for others and for you.  You can manage that yourself, or you can use "Auto Format" under the "Tools" menu in the Arduino IDE.
  • I recommend that you refrain from adding complexity to this code until you get the kurtosis calculation working.  Leave xbee stuff out of your program until you get kurtosis working.
  • Patience, Grasshopper.
124  Using Arduino / Programming Questions / Re: kurtosis calculations on an analog signal on: October 29, 2013, 11:39:58 am
Don't forget:  the first goal is to get the calculation working.  It's a whole lot easier to modify a working program than to start over with something new.  Fix this one, and worry about optimization and and improvements later.
125  Using Arduino / Programming Questions / Re: kurtosis calculations on an analog signal on: October 29, 2013, 08:15:10 am
Ingenious.  That's a lot of reasonable-looking code to come from a guy who didn't know where to start a few days ago.

Here are some suggestions:
  • [Edit:  Add this]
    Something's wrong with the timing and program flow.  The code decides when to take a sample, but it processes a sample regardless of whether or not it takes one.  Examine it:  loops starts; the test passes, it takes a sample, and processes it; loop terminates, and starts over; the test fails, and it doesn't take a sample, but it processes the last sample again anyway.  Most of that code needs to move into the "if(currentMillis ..." section, and the rest should only be executed when it's time to do final calculations and print.
  • You're trying to calculate a function of a series of values, and you don't yet know whether the calculation is correct.  You also don't know what the values are, since they're analog readings, and they aren't displayed.  Troubleshooting the calculation is difficult enough without having to wonder what the input data was.  While you're troubleshooting the calculation, use some convenient calculated data whose kurtosis is well-known, instead of analog readings.  Shutting off sample timing during troubleshooting will make the results show up faster.  Here are two suggestions:
Code:
xi = i  % 10
          // uniform distribution, expected excess kurtosis = -1.2
xi = sin(i*0.001*2*3.1415927*100) + 1
         // sine function, 100 Hz, sampled at 1/millisecond, expected excess kurtosis = -1.5

  • Decide whether you want to calculate kurtosis the old-fashioned way, or whether you want to calculate excess kurtosis.
  • Print some debugging information, like the value of the running average, fourth moment, and variance.  Be prepared to get deeper into the calculations if those values don't help.
  • Your "running average" technique, where newValue = alpha*sampleValue + (1-alpha)*oldValue, is a single-pole digital low-pass filter.  Its output value tends toward the mean of the input signal.  When you filter variance, you get something that looks like the statistical variance - the mean of the squares of the differences between the samples and the mean of the signal.  When you filter the fourth moment, you get something that looks like the fourth moment - the mean of the fourth power of those same differences.  Division by the number of samples is essentially accomplished in filtering those values.   Consequently, I'll recommend that you reconsider whether this line needs the multiplication by the number of samples:
Code:
 denominator = sigma4*numberSamples;
  • When you start getting output data, experiment with larger values of alpha.  I don't think it's necessary that alpha be the same as 1.0/numberSamples.  You might want to define beta  = 1.0 - alpha.
  • This looks to me to be an ingenious solution.  My experience with ingenious solutions to statistical calculations is that they often yield unpextected results, usually because there's some nugget of probability theory that I've overlooked that makes them invalid.  I can't see the flaw here, though - the level of filtering is pretty intense, and the signal mean will get pretty close to the actual value; once it stabilizes, I think that the variance and fourth moment calculations will be valid.  Nevertheless, I'd recommend testing it with several kinds of distributions to see that it gives the expected results, and be prepared for disappointment.
  • After you're confident of the kurtosis calculation, think about ways to mange the calculation of the signal mean.  When I run this code with known input data and print the value of runningaverage, it takes a while to stabilize.  Until it does, the output data will not be valid.  If the DC offset of the signal won't change during the measurement, consider instead taking some time to determine the signal mean while outputting no values, and then using that mean to calculate the second and fourth moments.  There's no loss of performance - there's a delay between startup and valid data either way.  With the mean known, the calculations are pretty simple.  Once the signal mean is established, I think that there's no necessity to filter the second and fourth moments - the calculation can be straightforward from the formula.
  • Consider AC-coupling the input signal.  The signal mean will then be the value of the analog offset voltage.  That'll give control of the signal mean to you, rather than to some setting on a sensor amplifier.  There are a lot of options for how to manage getting that voltage into the calculation, some involving hardware, some not.  A simple one would be to use a resistor divider to set it at half scale, and use that value as the initial value of runningaverage, rather than starting with zero.  That would reduce the time it takes for data to become valid, though possibly not by all that much - the second and fourth moments are still filtered.
  • As PaulS suggests, don't make sensorPin a float.  It seems to work, but it's just too weird.  sensorPin doesn't change, so it could easily be const int.
126  Using Arduino / Programming Questions / Re: kurtosis calculations on an analog signal on: October 28, 2013, 04:25:12 pm
It's good to see the original poster put up some code.  It suggests that he's actually interested in a solution.

The posted code doesn't compile.  There are repeated references to kurtvoltages, as if it were a variable. But kurtvoltages is an array, and, if it's going to be treated like a single value, it needs an index.

There are logic errors, too, but they can wait.  If it doesn't compile, you'll never get any results at all.

[Edit: Add this]
And, until you know what you're doing, please don't try to hook up an analog source - like a signal generator or a biological monitor - to your Arduino.  It can be quite easy to damage an analog input when the input voltage goes out of bounds.  I suspect that your signal source is centered at zero volts, and that it's negative for at least some of the time.  A negative voltage on an analog pin can damage it.

This sounds like an academic assignment.  Is it?
127  Using Arduino / Project Guidance / Re: Measuring AC line frequency on: October 08, 2013, 05:10:34 am
Here are three application notes from Atmel that might help:


128  Using Arduino / Programming Questions / Re: Multitasking? How? on: September 25, 2013, 04:44:43 pm
... when it increment to 256 it just starts outputting that value repeatedly.
I'd like to know why it "overflowed" ...

Here's how I see it:

The test that decides whether to print the "Meter Pulse Registered >>" message is a comparison between wattHourPulses and oldPulsesPer60swattHourPulses is unsigned long, and oldPulsesPer60s is byte.  oldPulsesPer60s will never be bigger than 255, while wattHourPulses can get really big.  Once wattHourPulses reaches 256, the test will always pass, and the message will print every time loop executes.  The speed of the serial interface will probably be what limits rate of the the output messages; at 115200, they'll come pretty fast.  If you let the program run until another pulse occurred, it would print " ... = 257," but it would print a whole lot of 256's before that happened.

The changes that you describe in reply #15 solve the problem by resetting wattHourPulses often enough to keep it from reaching 256 with a reasonable household load.  To hit 256 watt-hours in 60 seconds would take a total load of about 15.4 kW, which is quite a lot for a typical residence, but certainly not impossible.  I'd recommend declaring oldPulsesPer60s differently if you want to use the previous version of the code.

I pedantically note that the value reported as "kWh" is probably not labeled correctly.  If each pulse represents a watt-hour, then that value is in kW - energy per unit time, or power - rather than kWh.
129  Using Arduino / Programming Questions / Re: Multiple delayMicroseconds() inside interrupt function (weird behavior) on: September 16, 2013, 09:24:14 pm
I see it now:  I think that reply #1 says,
... how many thousands of microseconds have passed.  [emphasis added.]

while the quote from reply #2 says,
Quote
... how many thousands of milliseconds have passed.  [emphasis mine]

Idly speculating: I don't remember it, but I suspect that I typed the erroneous line and fixed it right away.  I can't find an edit tag on reply #1, but I notice that one doesn't attach when I edit something immediately.  That makes me suspect that AWOL sees that post by some means other than the one I use, and that the original error maintains a ghostly existence there.
130  Using Arduino / Programming Questions / Re: Summarizing analogRead() on: September 16, 2013, 12:17:36 am
How does the power company when they find customer-crafted circuits strapped to their meter?  In my neighborhood - Houston, TX, USA, Earth - they can be a bit suspicious, and they tend to think that alien stuff too close to the meter is intended to keep it from registering properly.
131  Using Arduino / Programming Questions / Re: Multiple delayMicroseconds() inside interrupt function (weird behavior) on: September 16, 2013, 12:07:27 am
Quote
microsmillis() uses the running count of Timer0 overflow interrupts to calculate how many thousands of milliseconds have passed.
That looks like a correction, but I'm not sure what it's correcting.  From wiring.c, IDE 1.5.3, as it compiles for the Uno, with declarations, compiler directives and housekeeping snipped for brevity:
Code:
unsigned long micros() {
... <snipped>
m = timer0_overflow_count;
t = TCNT0;
if ((TIFR0 & _BV(TOV0)) && (t < 255))
m++;
... <snipped>
return ((m << 8) + t) * (64 / clockCyclesPerMicrosecond());
}
timer0_overflow_count is bumped without further processing in the Timer0 overflow ISR; it's the running count of Timer0 overflows; it's used in calculating the return value of micros(); and it keeps track of - well, not exactly thousands of microseconds, but 1024's of microseconds.  micros(), rather than millis(), is the function the OP asked about.  The original quote, when I wrote it, said "microseconds," rather than "millseconds," and, as far as I can tell, the original was right.  Except for that part about "thousands," that is.

Is there something I'm not getting here?
132  Using Arduino / Programming Questions / Re: Multiple delayMicroseconds() inside interrupt function (weird behavior) on: September 13, 2013, 10:58:43 pm
Here's why:
  • While an interrupt service routine runs, other interrupts are disabled, unless the routine explicitly enables them.
  • micros() uses the running count of Timer0 overflow interrupts to calculate how many thousands of microseconds have passed.
  • While your interrupt service routine runs, Timer0 overflow interrupts aren't processed, so the count doesn't advance.
That means that the results of micros() are incorrect.  Calculations using those results will yield unexpected results.

If you're sure another Interrupt 0 won't occur while interrupt() runs, you could reenable interrupts inside of it, allowing the Timer0 interrupt service routine to execute.  Your delays will be a little long, since they won't account for the time spent servicing the Timer0 overflow ISR.

Alternatively, you could throw a flag in interrupt(), remove the delays from interrupt(), and execute the delays in loop().  That flag could be the value of micros() when the service routine executes; loop() could then just wait until micros() advances by 3000 from that value. 

It's generally a bad idea to use any delay - or any blocking call at all - inside an interrupt service routine.  Interrupt service routines need to execute quickly, to avoid interfering with other ongoing processes.

See "Hints for writing ISRs," down the page at this excellent url:  http://www.gammon.com.au/interrupts.
133  Using Arduino / General Electronics / Re: Turn your Arduino into a capacitor tester ... on: September 12, 2013, 11:19:23 pm
Empty not connected wires might be dangerous ?

Experience says that driving an unconnected pin doesn't appear to do any damage to the unit.  It could be because stray capacitances charge during the output pin's rise time, and never develop full VCC / R current.  It could be because stray capacitance to ground is only part of the generally uncharacterized output circuit; there's stray inductance, too.  It could be because the charge times, being much less than a cycle, are too short to matter.

Quote
... a pin without any visible capacitor but only a wire to a breadboard, not connected to anything. I get values like 29 pF, 50 pF ...
How long does the timer run to yield that result?   
134  Using Arduino / General Electronics / Re: Turn your Arduino into a capacitor tester ... on: September 11, 2013, 10:11:43 pm
... the resistor ratio as an argument for logarithm makes the result independent of the supply voltage Vcc provided it is constant.
I'm not sure I understand.  In the original project, the program measures the time it takes the capacitor voltage to go from ground to some reference voltage, established by a voltage divider.  When those voltages are equal, it stops the timer and makes the calculation.  The capacitor voltage as a function of time is
   VC(t) = V * ( 1 - e-t/RC )
The reference voltage is a constant:
   Vref = V * ( R1 / ( R1 + R2 ) )
Both are linear in V, the charging voltage, so setting them equal and dividing by V yields
   1 - e-t/RC = R1 / ( R1 + R2 )
The only variable in the whole thing is t, and V doesn't appear at all.  The calculation is independent of VCC already.

Solving the equation for C in terms of t yields
   C = t / (R * log( ( R2 + R1 ) / R2 ) )
When ( R2 + R1 ) / R2 ) is exactly e, the base of the natural logarithm, the log term reduces to 1, and the equation becomes
   C = t / R
The purpose of using the more complicated formula is to avoid the necessity of selecting resistors to get a ratio that's very close to e.  It lets us use a wider array of resistors, and we can select them for other reasons - maybe the simplest being that we have a couple of low-tolerance ones to hand.

Quote
For the best repeatability the power supply stability seems to be the key.
Indeed.  There's power supply jitter on a pin output, and plenty of jitter on VCC itself.  Power supply jitter shows up immediately on the reference voltage, while it's more or less integrated by the capacitor.  That'll lead to some degree of measurement error, and, to some extent, it'll be random.

Other sources of error are:
  • delay between turning on the charging pin and starting the timer,
  • propagation delay through the analog comparator,
  • comparator offset voltage, and
  • resistor tolerances in the charging resistor and the divider.
Those will have an impact on accuracy; they may not have much effect on repeatability.
135  Using Arduino / General Electronics / Re: Turn your Arduino into a capacitor tester ... on: September 10, 2013, 11:41:58 pm
What is "capacitive loading"?
Quote
The current drawn from capacitive loaded pins may be estimated (for one pin) as CL*VCC*f
With regard to this formula, a "capacitively loaded" pin charges and discharges a capacitor in the following fashion:
  • the capacitor's opposite terminal is connected to some constant voltage, usually - but not necessarily - VCC or GND;
  • the capacitor is connected to the pin through an impedance, which might be so small that it's effectively zero; and
  • the capacitor charges or discharges nearly completely each time the pin changes state.
This formula is useful for calculating the time-average current due to a capacitor connected to an output pin.  It's primarily useful for calculating power supply current.  [Edit: Add this]  For a grounded capacitor charged through a resistor, each time the output switches high, the power supply delivers Q = CL * VCC coulombs to fully charge the capacitor; when it switches low, those coulombs go to ground.  Switching high at f Hz, the total charge transferred in one second is CL * VCC * f.  That's in coulombs per second, the units of current, and it's the time-average current due to the pin as seen by the power supply.  The power supply only sees charging; discharge current doesn't pass through the supply.

It's less useful for calculating current through an output pin, and especially not useful for the purpose of determining whether the pin can safely support a particular current.  In particular, it doesn't describe either the maximum current or the RMS current.  

For a capacitance C connected to a pin through a resistance R and grounded on its other terminal:
  • the maximum current is VCC/R, and
  • the RMS current is sqrt( VCC2 * C * F / (2 * R) ), where F is the switching freqency.
The assumptions are that R is a lot bigger than the intrinsic impedance of the pins output driver, and that the capacitance charges and discharges nearly completely each time the output switches.  If R isn't large enough to make the pin's impedance is negligible, then some estimate of the pin resistance has to be added to the resistance value.  Accuracy will likely suffer, because the output resistance isn't a reported parameter of the IC, suggesting that it's not particularly well-controlled.  One noteworthy implication of these results is that the maximum current doesn't depend on the capacitance.

Quote
Does this mean that we could load and discharge the capacitor safely with the frequency of 10 kHz? The peak current may exceed even the absolute maximum of 40 mA, but "the average" current according to the above formula is only 5 mA.
It sounds like you're considering trying to limit the effective current through an output pin by rapidly switching the pin.  In terms of time-average current, that works; in terms of maximum current - as you noted - it doesn't.  Whether or not it's OK to exceed the published absolute maximum ratings for pin current has been repeatedly discussed on this forum with varying levels of chest-thumping and stupidity, mostly with high levels of both.  

Opinions vary.  Mine is that commercial devices designed to exceed published maxima should be clearly labeled, "Caveat emptor: might work for a little while, might not."  As for one-off gizmos intended for use by only their designers, I think that way madness lies: you can never entirely trust a device that's been overdriven.  It's almost certain to fail sooner or later, and it may fail softly, yielding incorrect results without obvious symptoms.

[Edit: spelling]
Pages: 1 ... 7 8 [9] 10 11 ... 25