Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I came up with solution, that from given set of possible denominators and nominators finds best approximation of given number.</p> <p>For example this set can contain all numbers that can be created by:<br> 1 &lt;= radicand &lt;= 100000<br> 1 &lt;= root_index &lt;= 20</p> <p>If set has N elements, than this solution finds best approximation in O(N log N). </p> <p>In this solution X represents denominator and Y nominator. </p> <ol> <li>sort numbers from set </li> <li>for each number X from set:<br> using binary find smallest Y such that Y/X >= input_number<br> compare Y/X with currently best approximation of input_number </li> </ol> <p>I couldn't resist and I implemented it:</p> <pre><code>#include &lt;cstdio&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; using namespace std; struct Number { // number value double value; // number representation int root_index; int radicand; Number(){} Number(double value, int root_index, int radicand) : value(value), root_index(root_index), radicand(radicand) {} bool operator &lt; (const Number&amp; rhs) const { // in case of equal numbers, i want smaller radicand first if (fabs(value - rhs.value) &lt; 1e-12) return radicand &lt; rhs.radicand; return value &lt; rhs.value; } void print() const { if (value - (int)value &lt; 1e-12) printf("%.0f", value); else printf("sqrt_%d(%d)",root_index, radicand); } }; std::vector&lt;Number&gt; numbers; double best_result = 1e100; Number best_numerator; Number best_denominator; double input; void compare_approximpation(const Number&amp; numerator, const Number&amp; denominator) { double value = numerator.value / denominator.value; if (fabs(value - input) &lt; fabs(best_result - input)) { best_result = value; best_numerator = numerator; best_denominator = denominator; } } int main() { const int NUMBER_LIMIT = 100000; const int ROOT_LIMIT = 20; // only numbers created by this loops will be used // as numerator and denominator for(int i=1; i&lt;=ROOT_LIMIT; i++) { for(int j=1; j&lt;=NUMBER_LIMIT; j++) { double value = pow(j, 1.0 /i); numbers.push_back(Number(value, i, j)); } } sort(numbers.begin(), numbers.end()); scanf("%lf",&amp;input); int numerator_index = 0; for(int denominator_index=0; denominator_index&lt;numbers.size(); denominator_index++) { // you were interested only in integral denominators if (numbers[denominator_index].root_index == 1) { // i use simple sweeping technique instead of binary search (its faster) while(numerator_index &lt; numbers.size() &amp;&amp; numbers[numerator_index].root_index &amp;&amp; numbers[numerator_index].value / numbers[denominator_index].value &lt;= input) { numerator_index++; } // comparing approximations compare_approximpation(numbers[numerator_index], numbers[denominator_index]); if (numerator_index &gt; 0) { compare_approximpation(numbers[numerator_index - 1], numbers[denominator_index]); } } } printf("Best approximation %.12lf = ", best_numerator.value / best_denominator.value); best_numerator.print(); printf(" / "); best_denominator.print(); printf("\n"); } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. PODecimal to Irrational fraction approximation
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJarosław Gomułka
    1. USJarosław Gomułka
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PODecimal to Irrational fraction approximation
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload