text:
301人阅读 评论(0)

# 1014. Waiting in Line (30)

400 ms

65536 kB

16000 B

Standard

CHEN, Yue

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

• The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
• Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
• Customer[i] will take T[i] minutes to have his/her transaction processed.
• The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while customer2 is served at window2. Customer3 will wait in front of window1 and customer4 will wait in front of window2. Customer5 will wait behind the yellow line.

At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.

Input

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (<=20, number of windows), M (<=10, the maximum capacity of each line inside the yellow line), K (<=1000, number of customers), and Q (<=1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output "Sorry" instead.

Sample Input
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7

Sample Output
08:07
08:06
08:10
17:00
Sorry

#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <queue>

using namespace std;

int t[1005];
int l;
int start[1005];
int e[1005];
int n,m;
int k;
void fun(int time)
{
int hh=time/60;
int mm=time%60;
printf("%02d:%02d\n",8+hh,mm);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&l);
for(int i=1;i<=k;i++)
scanf("%d",&t[i]);
int cnt=1;
memset(e,-1,sizeof(e));
queue<int> q[1005];
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
{
if(cnt>k)
continue;
if(j==1)
start[cnt]=0;
q[i].push(cnt++);
}
}
for(int i=0;i<540;i++)
{
int num=1e5;
for(int j=1;j<=n;j++)
{
if(q[j].empty()) continue;
int x=q[j].front();
if(start[x]+t[x]==i)
{
e[x]=i;
q[j].pop();
if(!q[j].empty())
{
int x=q[j].front();
start[x]=i;
}
}
}
if(cnt>k)
continue;
for(int j=1;j<=n;j++)
{
if(q[j].size()<m)
{
if(cnt>k)
continue;
if(q[j].empty())
start[cnt]=i;
q[j].push(cnt++);
}
}
}
for(int i=1;i<=n;i++)
{
if(!q[i].empty())
{
int x=q[i].front();
if(start[x]<540)
e[x]=start[x]+t[x];
}
}
int pos;
for(int i=1;i<=l;i++)
{
scanf("%d",&pos);
if(e[pos]==-1)
printf("Sorry\n");
else
fun(e[pos]);
}
return 0;

}
0
0

个人资料
• 访问：131069次
• 积分：4658
• 等级：
• 排名：第7453名
• 原创：349篇
• 转载：0篇
• 译文：0篇
• 评论：7条
阅读排行
最新评论


text:
Math Help - Accuracy of trig functions near asymptotes computer programming

1. Accuracy of trig functions near asymptotes computer programming

Hi all,

I have a question regarding the accuracy of trig functions with regard to computer programming.

Do the accuracy of trig functions change as the angle approaches the function's asymptotes?

For example; would the angle returned by arctan be less accurate for say a triangle with height 100000 and width .0000001 than say a triangle with height 10 and width 10. What I'm steering towards here is that as the function reaches it's asymptote does the accuracy reduce?

Likewise I'm wondering (but perhaps it's not as relevant) with Sin and Cos as they reach their maximum and minimum values of +1 and -1 do they lose accuracy as the function flattens out (as the derivate reaches zero).

Also with respect to computer programming we're using floating point calculations which have inherent inaccuracies. Does anyone have any thoughts on how this might all tie together?

In my early programming I used to construct static tables for performing integer math on sin (scaled up by 10000 etc or a power of 2) so I could do fast lookups, but I always avoided using tan lookups because of the amyptototes and thought I could not perform the integer math effectively.

Again any thoughts?

2. The usual risks are dividing by very small values (adding fake significance) or subtracting very similar values (losing significance). The specifics of your question rely on the specifics of your physical implementation. One would have to know EXACTLY how things are calculated. Exactly what algorithm is used to calculate sine, cosine, and tangent? For example, if the tangent is calculated directly (some kind of McLauren series, for example), that would be different than if the tangent is calculated from division of corresponding values of sine and cosine.

As a VERY ROUGH example, I started with McLauren expansions up through $x^{11}$ for sine, cosine, and tangent. I'll call these new functions s(x), c(x), and t(x) - where we expect t(x) = s(x)/c(x).

For x = 0 we get the very predictable:
s(0) = 0
c(0) = 1
t(0) = 0
s(0)/c(0) = 0

Not much interesting about that. With a McLauren expansion, we expect x = 0 to deliver exceptional results.

For $x = \frac{\pi}{4} < 1$ we get

$s\left(\frac{\pi}{4}\right) = 0.707106781179619$

$c\left(\frac{\pi}{4}\right) = 0.707106781071925$

Reference: $\frac{\sqrt{2}}{2} = 0.707106781186548$

$t\left(\frac{\pi}{4}\right) = 0.999792766967732$

$\frac{s(\frac{\pi}{4})}{c(\frac{\pi}{4})} = 1.00000000015230$

First, one might notice that c is NOT equal to s. This is because of the particular implementation. c(x) is an even function and s(x) has one higher order term. Recall that I quit at $x^{11}$. This makes c(x) actually quit at $x^{10}$, since it has no $x^{11}$. Neither is equal to the "exact" value.

Second, it is very clear that $t \neq s/c$. Frankly, the t(x) result is somewhat disappointing, giving only 3 decimal places exact. So we should prefer the quotient, right?

For $x = \frac{\pi}{2} > 1$ we get

$s\left(\frac{\pi}{2}\right) = 0.999999943741051$

$c\left(\frac{\pi}{2}\right) = -0.000000464766008$

$t\left(\frac{\pi}{2}\right) = 7.95774685489739$

$\frac{s(\frac{\pi}{2})}{c(\frac{\pi}{2})} = -2151620.22527681$

Now what?! The variations in tangent call into question what side of the asymptote we are on. For an asymptote, we would like a really big number (perhaps even the largest machine number), but I'm sure we'd be more comfortable with the sign not changing. Again, most of this error is a result of the SPECIFIC approximation. The McLauren expansion of tan(x) has ONLY positive terms. For x > 0, it cannot EVER produce a negative value. This, quite obviously, is not the case for sin(x)/cos(x).

What's the real answer to your question? That is very hard to say without a very clear understanding of the nature of your environment. The results shown here are specific to my implementation. Your results may differ, even in an attempt to reproduce what I have shown.

Note: Most implementations would have far sneakier algorithms than a simple McLauren expansion through $x^{11}$. Only the designers can tell you what is in there.

3. Originally Posted by Geoff M
Hi all,

I have a question regarding the accuracy of trig functions with regard to computer programming.

Do the accuracy of trig functions change as the angle approaches the function's asymptotes?

For example; would the angle returned by arctan be less accurate for say a triangle with height 100000 and width .0000001 than say a triangle with height 10 and width 10. What I'm steering towards here is that as the function reaches it's asymptote does the accuracy reduce?

Likewise I'm wondering (but perhaps it's not as relevant) with Sin and Cos as they reach their maximum and minimum values of +1 and -1 do they lose accuracy as the function flattens out (as the derivate reaches zero).

Also with respect to computer programming we're using floating point calculations which have inherent inaccuracies. Does anyone have any thoughts on how this might all tie together?

In my early programming I used to construct static tables for performing integer math on sin (scaled up by 10000 etc or a power of 2) so I could do fast lookups, but I always avoided using tan lookups because of the amyptototes and thought I could not perform the integer math effectively.

Again any thoughts?
If its done correctly arctan should give near full machine precision up to the point it goes out of normalisation/range.

RonL

format: plain


text:
# How can I use my Arduino together with an external power supply?

I am trying to design a simple square wave inverter (15V input from my power supply). For this purpose I will design a H-bridge with 4 MOSFETs controlled by the Arduino (5V or 3.3V output). The thing is, how can I make my power supply and Arduino work together? I only need the Arduino to control transistors (to make them let current pass).

Sorry for the bed design, as it is my first year in Electrical Engineering. This is the incomplete circuit design. The transistors in the scheme will be controlled by the Arduino. It will make blue ones OPEN first, then it will make red ones OPEN. So polarity will constantly change for the "Device." But I don't know how I can integrate the 5V Arduino here.

New contributor
İbrahim İpek is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• are you asking how to connect an Arduino to a 15 V power supply? ? – jsotola Feb 20 at 19:29
• No, I will power it from my PC. But I will also have to use a 15 V supply. Arduino is only there to control transistors and powering it with 15 V would burn it (?) – İbrahim İpek Feb 20 at 19:30

You connect the Arduino ground to the ground of your power supply and H-bridge driver. Make sure that the high currents have a direct ground path from the H-bridge back to the power supply and not through the Arduino's ground.

Figure 1. A simple driver circuit for H-bridge. Image source: Bristol Watch.

• Since the Arduino can only switch up to 5 V it cannot "reach high enough" to control Q1 and Q3. For this reason the 4.7k pull-up resistors are added and the 2N2222 transistors (or any small NPN) are added to turn on Q1 and Q3.
• Note that Q1 and Q3 are PMOS; Q2 and Q4 are NMOS. Your design shows four NMOS. You can do that but the switching circuit will be more complex.
• Connect Arduino ground to H-bridge ground.
• Can you please give me a visual illustration? Sorry, I am very new to electronics and my native language is not English either. – İbrahim İpek Feb 20 at 19:31
• If you edit your question to show your H-bridge design I can edit my answer. Your English is good. – Transistor Feb 20 at 19:35
• Okay, lemme try – İbrahim İpek Feb 20 at 19:43
• Done @Transistor – İbrahim İpek Feb 20 at 20:01
• @İbrahimİpek See the update. – Transistor Feb 20 at 20:46

Different machines/circuits can connect their SIGNALS together while having different power cables with different voltages running to them. What matters in this case is that the signal ports connecting to each other can handle each other.

More applicable for your H-bridge is below. Inside the MOSFET transistor is a barrier between the gate and the rest of the MOSFET. That barrier blocks the 15V from getting to the 3.3V (within reason). It allows a smaller signal applied between the gate and source terminals to control a larger signal across the drain and source terminals.

The base terminal of a BJT (another common type of transistor) is similar.

simulate this circuit – Schematic created using CircuitLab

• Thanks, this makes sense. So just plugging my Arduino to my PC and the output pin to gate will be enough? – İbrahim İpek Feb 20 at 20:04
• The MOSFET is not controlled by the voltage at the gate. This is impossible because voltage is measured between two points. The MOSFET is controlled by the voltage BETWEEN the gate and source terminals. So in the example above, your Arduino pin needs to connect to the gate and the GND. However, you will quickly notice that in an H-bridge not all MOSFETs have their source terminals connected to the GND of the Arduino. This is an issue that you will need to deal with known as "high-side gate drive" which is another topic for another question once you look into it more. – DKNguyen Feb 20 at 20:07
• The MOSFET only cares about and can only "see" the voltage between its terminals. If the MOSFET's source terminal is not connected to GND, and you apply a gate voltage that is referenced to GND, the MOSFET cannot know what that voltage is because it cannot see GND. It only knows what voltage is appearing across gate-source. – DKNguyen Feb 20 at 20:07
• In that case upper two MOSFETs will fail to work. Hmm... Can I solve it by simply using a BJT (although it is not good for frequency)? Or should I go for what you call "High-Side Gate Drive"? – İbrahim İpek Feb 20 at 20:33
• I uploaded a photo above if you have not seen it, I am talking in terms of it – İbrahim İpek Feb 20 at 20:35


text:
The Differential Form of Maxwell's Equations

Having a thorough understanding of the differential operations provides students with a concrete means by which to interpret Maxwell's equations and transition from the integral to differential form of the equations. The sequence is split into two parts which separately address divergence and curl to build to the Gauss and Ampere Maxwell equations for both electric and magnetic fields. This sequence is assuming static fields and therefore does not build time dependence into Maxwell's equations.

Geometric understanding of divergence as a flux per unit volume allows students to physically interpret two of Maxwell's equations. For instance, the divergence of the electric field indicates the charge density at a particular location in the electric field by $\vec{\nabla} \cdot \vec{E} = \frac{\rho}{\epsilon_0}$. In the absence of charge, the divergence of the electric field must be zero. Similarly, the divergence of the magnetic field, $\vec{\nabla}\cdot\vec{B}=0$, is always zero because there are no magnetic monopoles.

Geometric understanding of the curl as a circulation per unit area also provides a means for student to physically interpret two of Maxwell's equations. The curl of a static magnetic field is related to the current density by $\vec{\nabla} \times \vec{B} = \mu_0 \vec{J}$ which means the curl is non-zero at the location of a current density and zero where there is no current density. The corresponding equation for electric field states that the curl of a static electric field is zero, $\vec{\nabla}\times \vec{E} = 0$.

Activities: Gauss's Law

• The Geometry of Flux Sequence (Estimated time: 20-50 minutes): This sequence of activities emphasizes the geometry of flux through three activities and then has an activity where students use Gauss's law in integral form to find the electric field of various charge distributions. Understanding the geometry of flux allows students to understand and effectively use Gauss's law in integral form.
• Definition of Divergence Lecture (Estimated time: 20 minutes): Divergence is introduced as a flux per unit volume at a specific point in a vector field.
• Visualizing Divergence (Estimated time: 20 minutes): Students use a Mathematica notebook to look at various vector fields and use the idea of divergence as a flux per unit volume to determine whether the divergence at a specific point in the vector field is positive, negative, or zero. This activity emphasizes the geometry of divergence by engaging students in thinking about how divergence and flux are related.
• Proof of Divergence Theorem Lecture: We follow “div, grad, curl and all that”, by Schey. The Divergence theorem is almost a lemma based on the definition of divergence. Draw a diagram of an arbitrary volume divided into lots of little cubes. Calculate the sum of all the fluxes out of all the little cubes (isn't this a strange sum to consider!!) and argue that the flux out of one cube is the flux into the adjacent cube unless the cube is on the boundary.
• Differential Form of Gauss's Law Lecture: At this point, following the activities and lectures involving divergence and the Divergence theorem, it is important for students to understand the significance of the differential form of Maxwell's equations which involve divergence. Students should understand $\vec{\nabla}\cdot\vec{E}=\frac{\rho}{\epsilon_0}$ as a way in which to determine a charge density in an electric field. The divergence of an electric field will be zero at a point with no charges, but it will be non-zero at a point where there is a charge density. Although the divergence of a magnetic field, $\vec{\nabla}\cdot\vec{B}=0$, was not explicitly explored in the preceding activities, this is a good point at which to discuss that zero divergence of a magnetic field means there are no magnetic monopoles.

Activities: Ampere's Law

• Visualizing Curl (Estimated time: 20 minutes): Students use a Mathematica notebook to look at various vector fields to determine the sign of the curl of a vector field at a particular point. Students use the geometric concept of curl as circulation per unit area to determine whether the curl is negative, positive, or zero at a specific point in the vector field. Students should have some familiarity with curl in rectangular coordinates from an earlier brief lecture or from mathematics coursework prior to this activity
• Definition of Curl Lecture: Curl is introduced as a circulation per unit area at a specific point in a vector field. This lecture serves as a thorough introduction to curl in rectangular, cylindrical, and spherical coordinates by building from the Visualizing Curl activity.
• Derivation of Stokes' Theorem Lecture: Following “div, grad, curl and all that” by Schey, this lecture derives Stokes' theorem by
• Differential Form of Ampere's Law Lecture:

Views

New Users

Curriculum

Pedagogy

Institutional Change

Publications


text:
Piecewise functions: Got an example of a real world piecewise function?

Looking for something beyond a contrived textbook problem concerning jelly beans or equations that do not represent anything concrete. Not just a piecewise function for its own sake. Anyone?

• I use b-splines for some image processing work. These are piecewise polynomial functions and very useful I might add! – WimC Jun 5 '12 at 12:37
• Piecewise what? Piecewise defined, piecewise linear, piecewise continuous... – Simon Markett Jun 5 '12 at 12:37
• And if you are going for full on real life: The marginal tax rate is piecewise linear (at least in some countries) – Simon Markett Jun 5 '12 at 12:40
• @SimonMarkett: I think you mean the marginal tax rate is piecewise constant, so that the amount of tax to be payed itself is a piecewise linear function of the income. What you sugfgest would make the tax amount piecewise quadratic, which would be fun (sort of) but is not common. – Marc van Leeuwen Jun 5 '12 at 14:19
• @MarcvanLeeuwen, yes you are right. Since I don't pay tax yet I just vaguely remembered the graph as it was shown to us back in high school and probs confused it. Luckily I am still right strictly speaking, since any constant function is linear :P – Simon Markett Jun 5 '12 at 14:25

Something like "buy $5$, and get each one after that at half price" say at a grocery store or clothing store. For example, let $C(x)$ be the cost of the item for the consumer and $p(x)$ be the price (assume it is constant.)

Then,

$C(x) = 5p |x\le5$ or $C(x) = 5p + (x-5)\cdot\frac{1}{2}p|x>5$

• Are we assuming that the customer is not allowed to buy one item at the price $p$? – ahorn Apr 28 '16 at 20:39

I always thought the horizontal distance from a wall to an object is a good example of a piecewise continuous function (of the height):

Here the various red lines show the various distances and the green line marks the point of discontinuity.

Computing income taxes in a bracketed system.

Cab fares are a piecewise constant function of distance travelled.

• They charge for time, too! – The Chaz 2.0 Jun 5 '12 at 13:05

The classic example is friction---say for a block sitting on a rough horizontal plane and subject to a continuously increasing horizontal force. The frictional force rises steadily to match the applied force, and then it drops back a bit to a constant value when the block begins to slide.

• Though this, like every example from physics, is of course just an approximation. If you measure precise and quickly enough, the drop of the frictional force is really just a fuzzy transition, governed by randomness (thermal fluctuations). – leftaroundabout Jun 5 '12 at 17:51
• @leftroundabout: If you measure even more precisely and quickly, you will get only discrete (quantized) transitions in the output of your measuring device. – John Bentin Jun 5 '12 at 20:50
• Close to absolute zero temperature / in a closed system yes, but not at the conditions where you would usually measure something like friction. Force isn't much good as a quantum-mechanical observable anyway. – leftaroundabout Jun 5 '12 at 22:46
• Is this also called static vs dynamic friction ? – JackOfAll Sep 17 '14 at 12:10
• @JackOfAll: Yes. – John Bentin Sep 17 '14 at 16:36

How about a monthly mobile phone plan? Your cost is constant (maybe $50/month) as long as you stay under the allotted minutes (maybe 1000/month), but then you are charged per minute after. Shock waves. Properties of materials before and after phase transitions. Any disturbed physical system. If you're dealing with circuits you'll often want to solve an equation that involves switches. E.g, letting a capacitor charge for 1 ms and then switching the connection to a closed loop where it discharges. That switch naturally gives a piecewise-defined function. Similar ideas go for physical systems involving collisions, such as a bouncing ball. They come up all the time. Depth of a swimming pool as function of the distance from one end: As Wim mentions in the comments, piecewise polynomials are used a fair bit in applications. In designing profiles and shapes for cars, airplanes, and other such devices, one usually uses pieces of Bézier or B-spline curves (or surfaces) during the modeling process, for subsequent machining. In fact, the continuity/smoothness conditions for such curves (usually continuity up to the second derivative) are important here, since during machining, an abrupt change in the curvature can cause the material for the modeling, the mill, or both, to crack (remembering that velocity and acceleration are derivatives of position with respect to time might help to understand why you want smooth curves during machining). Postal rates (as a function of weight, in ounces): Look at the price of a$1.9$oz letter, then$1.99$oz letter, then$2.01$oz letter, etc. Piecewise constant functions come up all the time in the design and analysis of digital circuits (see square waves, for example). The finite element method is a very widely used technique that approximates solutions of differential equations as piecewise linear functions. What about the travel time to a fixed destination in a scheduled public transport system? It is a piecewise linear function of the departure time with slope$-1\$.

Bussiness is a good example. The increase in salary shows a piecewise function.

I liked the rates in a parking garage as a step function or there is the wages at a job - when you include overtime you have a piecewise function of your pay as a function of the hours you worked.

The free-fall acceleration on and in the earth must be modeled piece-wise, even in the simplest model of constant density.

Body must be at least 30 characters.

You want to visit two shops in the High Street. You drive your car to the High Street, park it, walk to each shop and back to your car. What distance do you have to walk as a function of where you park?


text:
# Matplotlib Examples: Plots with String Axis Labels

Last updated:

WIP Alert This is a work in progress. Current information is correct but more content may be added in the future.

## Bar plot

Full code available here

Just call plt.xticks(x_values, labels).

Example: use months of the year as the x-axis labels

import matplotlib.pyplot as plt
import numpy as np

# generate sample data for this example
xs = [1,2,3,4,5,6,7,8,9,10,11,12]
ys = np.random.normal(loc=3.0,size=12)
labels = ['jan','feb','mar','apr','may','jun','jul','aug','sept','oct','nov','dec']

plt.bar(xs,ys)

# HERE tell pyplot which labels correspond to which x values
plt.xticks(xs,labels)

If you don't set labels,
each label is the value itself

Set string labels using plt.xticks(xs,labels)

## Horizontal bar plot

Full code available here

Example: using the months of the year as the y-axis in a horizontal bar plot

import matplotlib.pyplot as plt
import numpy as np

# generate sample data for this example
xs = [1,2,3,4,5,6,7,8,9,10,11,12]
ys = np.random.normal(loc=3.0,size=12)
labels = ['jan','feb','mar','apr','may','jun','jul','aug','sept','oct','nov','dec']

plt.barh(xs,ys)

# HERE tell pyplot which labels correspond to which x values
plt.yticks(xs,labels)

Horizontal bar plots are a useful alternative
when there is not enough space for labels
on the x (horizontal) axis

## Set labels for individual Axes

TODO


text:
mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)

 charybdis 2021-01-11 23:07

According to jasonp the CADO filtering format has [URL="https://mersenneforum.org/showthread.php?t=22624"]changed[/URL] since that code was written. An old version of CADO could work but I don't know whether it had been sufficiently tested on jobs this big back then, and this would certainly have been before the multithreaded merge code was written.

 ryanp 2021-01-11 23:08

So I successfully cloned the latest CADO repo and built the replay binary, but not quite sure how to invoke it.

[CODE]The available parameters are the following:
-purged input purged file
-his input history file
-out basename for output matrices
-skip number of heaviest columns that go to the dense matrix (default 32)
-index file containing description of rows (relations-sets) of the matrix
-ideals file containing correspondence between ideals and matrix columns
-force-posix-threads (switch) force the use of posix threads, do not rely on platform memory semantics
-path_antebuffer path to antebuffer program
-for_msieve (switch) output matrix in msieve format
-Nmax stop at Nmax number of rows (default 0)
-col0 print only columns with index >= col0
-colmax print only columns with index < colmax
-verbose_flags fine grained control on which messages get printed[/CODE]

I've got an input.dat.gz containing all my relations (gzipped) and already have msieve's input.fb and input.ini. Any advice?

 chris2be8 2021-01-12 16:36

fivemack wrote a program called remsing to remove singleton relations. It might help.

Chris

 ryanp 2021-01-12 18:33

[QUOTE=chris2be8;569069]fivemack wrote a program called remsing to remove singleton relations. It might help.

Chris[/QUOTE]

Thanks - to be clear, is the suggestion that after "remdups4" (I now have ~2.1B uniques) to then run that through remsing before handing the relations to msieve?

 VBCurtis 2021-01-12 18:55

Yes. The idea, I think (?) is to run the first pass of singleton removal externally, so msieve handles a smaller dataset. This speeds things up when e.g. trying a handful of target densities, and in the case where relations counts are really big like this job it may help msieve handle the dataset.

You can run it multiple times, just like msieve runs multiple singleton-removal passes, but I found a single run helpful for the GNFS-207 team-sieve job.

 ryanp 2021-01-12 19:01

I've got it running now. The output is currently at:

[CODE]$~/remsing/remsing input.dat input.rem 1449910000 read 1102385169 bad[/CODE] Does that ration of "bad" to "read" seem reasonable?  VBCurtis 2021-01-12 19:09 No. The numbers should look quite similar to the first pass of msieve, such as these from your log on 9th Jan: [code]commencing in-memory singleton removal begin with 2069585205 relations and 2015728165 unique ideals reduce to 940662702 relations and 730460437 ideals in 20 passes[/code] Using this log as a very rough guide, you should get output of about half your input for the first pass through remsing. Edit: I think that happened to me the first time I tried it; an updated remsing was later posted that worked fine for me. The link posted here was to the post #608 that had the updated remsing, though. Hrmmm.....  ryanp 2021-01-12 20:49 [QUOTE=VBCurtis;569099]No. The numbers should look quite similar to the first pass of msieve, such as these from your log on 9th Jan: [code]commencing in-memory singleton removal begin with 2069585205 relations and 2015728165 unique ideals reduce to 940662702 relations and 730460437 ideals in 20 passes[/code] Using this log as a very rough guide, you should get output of about half your input for the first pass through remsing. Edit: I think that happened to me the first time I tried it; an updated remsing was later posted that worked fine for me. The link posted here was to the post #608 that had the updated remsing, though. Hrmmm.....[/QUOTE] I just grabbed the latest code from [url]https://github.com/fivemack/factorisation-tools[/url]. Maybe fivemack (if he's reading this) can chime in? The final output was about 1/4 the original rels, which definitely seems wrong.  charybdis 2021-01-12 21:13 Another suggestion: if the huge volume of relations is posing problems for msieve, then you could try turning this into a 33/35 job by removing all the relations with 36-bit algebraic factors using grep. Granted, you might need to sieve a bit more, but it ought to be simpler than finding and fixing a bug.  VBCurtis 2021-01-12 22:06 Or, you could just let CADO run the filtering and see how big that matrix is. I think msieve generally creates a matrix slightly bigger than cado; so if CADO's matrix comes out a tolerable size, you can stop sieving and focus on getting the dataset through msieve. Though, Charybdis' last suggestion might mean sieving a little more anyway if msieve proves to be the problem.  ryanp 2021-01-13 00:02 [QUOTE=VBCurtis;569117]Or, you could just let CADO run the filtering and see how big that matrix is.[/QUOTE] I would, but I'm not quite sure how to run the replay binary? (also I thought there was some question about current. compatibility between CADO's output and msieve's LA?) In any event, here's where things currently stand with the latest msieve run, 2.1B unique's and target_density=110: [CODE]Tue Jan 12 12:21:48 2021 found 11 duplicates and 2110664553 unique relations Tue Jan 12 12:21:48 2021 memory use: 31280.0 MB Tue Jan 12 12:21:49 2021 reading ideals above 1591017472 Tue Jan 12 12:21:49 2021 commencing singleton removal, initial pass Tue Jan 12 16:06:06 2021 memory use: 41024.0 MB Tue Jan 12 16:06:07 2021 reading all ideals from disk Tue Jan 12 16:07:00 2021 memory use: 39808.5 MB Tue Jan 12 16:08:59 2021 commencing in-memory singleton removal Tue Jan 12 16:10:33 2021 begin with 2110664552 relations and 2029607823 unique ideals Tue Jan 12 16:27:46 2021 reduce to 992995519 relations and 761340257 ideals in 20 passes Tue Jan 12 16:27:46 2021 max relations containing the same ideal: 35 Tue Jan 12 16:28:38 2021 reading ideals above 720000 Tue Jan 12 16:28:38 2021 commencing singleton removal, initial pass[/CODE]  ryanp 2021-01-14 21:39 msieve keeps getting wedged... Trying again with 2.1B uniques and target_density=90.  henryzz 2021-01-15 12:24 Would jasonp be able to give any advice on how to get past this blockage in the merge stage? I don't know whether he is reading this thread.  wreck 2021-01-15 14:59 I'd suggest to do the 'NFS Filtering' step 50 hours first , to look what will happen then. Since the relations count is 2000 million, it will meed more patience than 1000 million.  wreck 2021-01-15 15:06 Repeate messages. Some background date: 1. filter step for 2,1076+ snfs 324 (688M relations) : 15 hours. 2. filter step for 10,459- snfs 306 (737M relations) : 22 hours.  ryanp 2021-01-15 16:48 [QUOTE=wreck;569361]I'd suggest to do the 'NFS Filtering' step 50 hours first , to look what will happen then. Since the relations count is 2000 million, it will meed more patience than 1000 million.[/QUOTE] Thanks for the tip! I'll try to let this run (with 2.1B uniques and TD=90) sit for a while.  ryanp 2021-01-18 21:49 [CODE]Fri Jan 15 12:21:24 2021 commencing in-memory singleton removal Fri Jan 15 12:22:01 2021 begin with 590365520 relations and 594141896 unique ideals Fri Jan 15 12:35:29 2021 reduce to 585813821 relations and 580608996 ideals in 21 passes Fri Jan 15 12:35:29 2021 max relations containing the same ideal: 155 Fri Jan 15 12:37:14 2021 relations with 0 large ideals: 307095 Fri Jan 15 12:37:14 2021 relations with 1 large ideals: 215009 Fri Jan 15 12:37:14 2021 relations with 2 large ideals: 1852650 Fri Jan 15 12:37:14 2021 relations with 3 large ideals: 10607404 Fri Jan 15 12:37:14 2021 relations with 4 large ideals: 38306704 Fri Jan 15 12:37:14 2021 relations with 5 large ideals: 90474854 Fri Jan 15 12:37:14 2021 relations with 6 large ideals: 141486075 Fri Jan 15 12:37:14 2021 relations with 7+ large ideals: 302564030 Fri Jan 15 12:37:14 2021 commencing 2-way merge[/CODE] So we're now at 72+ hours and it's still running... I'll give it a few more days, but starting to lose hope.  pinhodecarlos 2021-01-18 22:23 Maybe get in touch with Greg from NFS@Home to see if he can give any support or advise?!  charybdis 2021-01-18 22:49 How's CPU usage looking? Is msieve actually doing anything or is it just hanging? And while we're at it, how's memory usage?  frmky 2021-01-19 05:43 [QUOTE=pinhodecarlos;569622]Maybe get in touch with Greg from NFS@Home to see if he can give any support or advise?![/QUOTE] This is well outside of anything I've run. My largest has been about 1 billion relations. However, if the relations are available online to download I'll be happy to play with it.  wreck 2021-01-19 10:13 If possible , could you give it another try with unique relations less than 1600M? As a comparison, VBCurtis done 2,2330L (gnfs 207) with 162M unique relations. And , in my memory, there is a time that fivemack finish a nfs job using relations count 720M successfully, while 800M failed (using lpb33 ). A rough guess is that sometimes ago, there is a barrier near 800M, now it jump to 1600M for some reason.  VBCurtis 2021-01-19 15:18 No, I didn't use 162M uniques. Did you miss a zero? This job is tougher than the GNFS-207 by quite a lot, and uses bounds which are expected to require more relations (36/33 should require more than 35/34). 2e9 relations may not be enough, but is quite surely not too many. Citing relations counts for 33-lp jobs is totally irrelevant to this job, which is using much larger bounds. The number of relations left heading into merge shows rather clearly that this is not oversieved. There is no reason to think the old msieve large-dataset bug is the culprit here. However, Charybdis' idea to cull all 36-bit-large-prime relations from the dataset and try to filter as a 33/35 job has merit.  ryanp 2021-01-19 15:25 [QUOTE=VBCurtis;569670]There is no reason to think the old msieve large-dataset bug is the culprit here. However, Charybdis' idea to cull all 36-bit-large-prime relations from the dataset and try to filter as a 33/35 job has merit.[/QUOTE] I'm willing to try culling the 36-bit large prime relations. Would you be able to construct the "grep" command? I don't quite know the msieve relation format well enough.  charybdis 2021-01-19 15:47 [QUOTE=ryanp;569671]I'm willing to try culling the 36-bit large prime relations. Would you be able to construct the "grep" command? I don't quite know the msieve relation format well enough.[/QUOTE] [C]grep -v ",[8-9a-f]........$"[/C] should remove all lines ending with a 36-bit prime, which is what we need.

 frmky 2021-01-23 22:13

There's definitely an msieve filtering bug. Good to have a data set that triggers it. Unfortunate that msieve needs to run for 15 hours to trigger it. Let's see what gdb says...

[CODE]commencing singleton removal, initial pass
memory use: 41024.0 MB
memory use: 39309.4 MB
commencing in-memory singleton removal
begin with 2074342591 relations and 1985137022 unique ideals
reduce to 992888838 relations and 765115141 ideals in 20 passes
max relations containing the same ideal: 35
commencing singleton removal, initial pass
memory use: 21024.0 MB
memory use: 46989.5 MB
keeping 913886427 ideals with weight <= 200, target excess is 5352837
commencing in-memory singleton removal
begin with 992888838 relations and 913886427 unique ideals
reduce to 992241034 relations and 913238552 ideals in 15 passes
max relations containing the same ideal: 200
removing 8630643 relations and 8331224 ideals in 2000000 cliques
commencing in-memory singleton removal
[kepler-0-0:29616] *** Process received signal ***
[kepler-0-0:29616] Signal: Segmentation fault (11)
[kepler-0-0:29616] Signal code: Address not mapped (1)
[kepler-0-0:29616] [ 1] ./msieve993_new[0x43ffd0]
[kepler-0-0:29616] [ 2] ./msieve993_new[0x463ae7]
[kepler-0-0:29616] [ 3] ./msieve993_new[0x43c2fb]
[kepler-0-0:29616] [ 4] ./msieve993_new[0x4288dd]
[kepler-0-0:29616] [ 5] ./msieve993_new[0x415bc4]
[kepler-0-0:29616] [ 6] ./msieve993_new[0x405b1b]
[kepler-0-0:29616] [ 7] ./msieve993_new[0x404987]
[kepler-0-0:29616] [ 8] ./msieve993_new[0x40454c]
[kepler-0-0:29616] [ 9] /lib64/libc.so.6(__libc_start_main+0xf5)[0x7eff11f03c05]
[kepler-0-0:29616] [10] ./msieve993_new[0x4045f2]
[kepler-0-0:29616] *** End of error message ***[/CODE]

 wreck 2021-01-25 01:21

Could you compile a debug version to see
which line it crashing?

 frmky 2021-01-27 02:42

We’re in filter_purge_singletons_core() at common/filter/singleton.c:441, looping through the relations counting the number of times that each ideal occurs. But the last relation is broken! We’re at the last relation since i = num_relations-1. The ideal_list for this last relation contains entries greater than num_ideals. Don’t know why though… Probably an overflow somewhere. But where? Trying to track it down but might take a while since I don't have a lot of time to devote to this and individual tests take a day.

found 578077506 hash collisions in 2074342600 relations
commencing duplicate removal, pass 2
found 9 duplicates and 2074342591 unique relations
memory use: 16280.0 MB
commencing singleton removal, initial pass
memory use: 41024.0 MB
memory use: 39309.4 MB
commencing in-memory singleton removal
begin with 2074342591 relations and 1985137022 unique ideals
reduce to 992888838 relations and 765115141 ideals in 20 passes
max relations containing the same ideal: 35
commencing singleton removal, initial pass
memory use: 21024.0 MB
memory use: 46989.5 MB
keeping 913886427 ideals with weight <= 200, target excess is 5352837
commencing in-memory singleton removal
begin with 992888838 relations and 913886427 unique ideals
reduce to 992241034 relations and 913238552 ideals in 15 passes
max relations containing the same ideal: 200
removing 8630643 relations and 8331224 ideals in 2000000 cliques
commencing in-memory singleton removal

Program received signal SIGSEGV, Segmentation fault.
0x000000000044a178 in filter_purge_singletons_core (obj=0x6de250, filter=0x7fffffffc710) at common/filter/singleton.c:441
441 freqtable[ideal]++;
Missing separate debuginfos, use: debuginfo-install glibc-2.17-196.el7_4.2.x86_64 gmp-6.0.0-15.el7.x86_64 zlib-1.2.7-17.el7.x86_64
(gdb) backtrace
#0 0x000000000044a178 in filter_purge_singletons_core (obj=0x6de250, filter=0x7fffffffc710) at common/filter/singleton.c:441
#1 0x0000000000475e26 in filter_purge_cliques (obj=0x6de250, filter=0x7fffffffc710) at common/filter/clique.c:646
#2 0x0000000000443cf6 in filter_make_relsets (obj=0x6de250, filter=0x7fffffffc710, merge=0x7fffffffc6e0, min_cycles=5352837)
at common/filter/filter.c:65
#3 0x000000000042f0fb in do_merge (obj=0x6de250, filter=0x7fffffffc710, merge=0x7fffffffc6e0, target_density=130)
at gnfs/filter/filter.c:187
#4 0x000000000042fad0 in nfs_filter_relations (obj=0x6de250, n=0x7fffffffc960) at gnfs/filter/filter.c:411
#5 0x00000000004172ac in factor_gnfs (obj=0x6de250, input_n=0x7fffffffcb40, factor_list=0x7fffffffcbd0) at gnfs/gnfs.c:153
#6 0x0000000000404dcd in msieve_run_core (obj=0x6de250, n=0x7fffffffcb40, factor_list=0x7fffffffcbd0) at common/driver.c:158
#7 0x00000000004051b4 in msieve_run (obj=0x6de250) at common/driver.c:268
#8 0x00000000004038a4 in factor_integer (
buf=0x7fffffffd650 "38315657995194363034877423503084547947166751578940985843521212522635100246118059073205923746544331860205171086654671434719340358393954962433533212457600196112076644876654207767427267797808629935905445"..., flags=1027, savefile_name=0x0,
logfile_name=0x0, nfs_fbfile_name=0x0, seed1=0x7fffffffd64c, seed2=0x7fffffffd648, max_relations=0, cpu=cpu_core,
cache_size1=32768, cache_size2=20971520, num_threads=0, which_gpu=0, nfs_args=0x7fffffffdcee "target_density=130") at demo.c:235
#9 0x00000000004046bd in main (argc=4, argv=0x7fffffffd988) at demo.c:601
(gdb) info frame
Stack level 0, frame at 0x7fffffffc340:
rip = 0x44a178 in filter_purge_singletons_core (common/filter/singleton.c:441); saved rip 0x475e26
called by frame at 0x7fffffffc370
source language c.
Arglist at 0x7fffffffc2b8, args: obj=0x6de250, filter=0x7fffffffc710
Locals at 0x7fffffffc2b8, Previous frame's sp is 0x7fffffffc340
Saved registers:
rip at 0x7fffffffc338
(gdb) info locals
ideal = 2057043263
i = 983610390
j = 5
relation_array = 0x7ff47e0f1010
curr_relation = 0x7ffc79bde3a0
old_relation = 0x7f1fd8001e8480
orig_num_ideals = 913238552
num_passes = 32767
num_relations = 983610391
num_ideals = 913238552
new_num_relations = 8630643
(gdb) print *curr_relation
$2 = {rel_index = 15834702, ideal_count = 36 '$', gf2_factors = 69 'E', connected = 156 '\234', ideal_list = {885450581, 598542783,
158747510, 638930804, 786848709, 2057043263, 3845, 186587920, 18476918, 67526419, 598542783, 872055544, 2057043265, 2046824196,
3942562, 102078889, 58908383, 865042570, 2057043267, 872418055, 9125741, 85351335, 11880544, 43981132, 865042570, 873512089,
893921179, 2057043271, 2567, 93072473, 26460704, 33365801, 865042570, 517341201, 275602560, 862343378, 2057043273, 83889159,
66167424, 46818875, 59842776, 59333874, 194384291, 865042570, 172206968, 2057043276, 50334725, 905653709, 628443801, 865042570,
801305779, 869019178, 2057043277, 2046821898, 20184373, 101514515, 16353075, 87715774, 36505563, 58989284, 865042570, 598565998,
334060622, 469101029, 2057043280, 83889158, 73623668, 106612925, 359795440, 9473259, 157931537, 772472752, 2057043282, 218106376,
140592574, 157045250, 477152215, 866943502, 6146950, 41607604, 44380953, 772472752, 2057043284, 150998022, 105306193, 842728936,
7879065, 444703037, 772472752, 403730401, 2057043289, 83889414, 320662844, 329981033, 248067990, 772472752, 23316642, 631501233,
2057043290, 822087174}}
(gdb)
[/CODE]

 wreck 2021-01-31 05:49

(1767 code line read, folder common/filter, file singleton.c, clique.c, etc.),
this filter problem seems not easy to solve.
But here are some thinkings.

1. From common/filter/filter_priv.h
The definition of ideal_map_t is
typedef struct {
uint32 payload : 30; /* offset in list of ideal_relation_t
structures where the linked list of
ideal_relation_t's for this ideal starts */
uint32 clique : 1; /* nonzero if this ideal can participate in
a clique */
uint32 connected : 1; /* nonzero if this ideal has already been
added to a clique under construction */
} ideal_map_t;
If the ideal is more than 1000M in function purge_cliques_core(),
it is possible that the filter would not work properly.
Here when entering into purge_cliques_core function, the
relation count is 992888838, less than 2^30, so here this 30 bit should not
be the reason of the crash.

2.
2057043265 = 0x7A98FD41
0x3A98FD41 = 983104833
This number is near the num_relations (983610391).
It is possible that the ideal_map_t.clique bit is not cleared propered
in function purge_cliques_core().
But this is also a guess.

3. In function filter_purge_singletons_core().
curr_relation->ideal_count is 36, but there are 3 values
in curr_relation->ideal_list is the same (865042570).
curr_relation->ideal_list[17]
curr_relation->ideal_list[24]
curr_relation->ideal_list[32]
It is a little strange.

4. In function purge_cliques_core(), Line 370
the variable num_reverse is possiblly exceed 2^32,
while its type is uint32.

5. A question.
Does ryanp give a try to use unique relations less than 1600M?
If done, what's the result?

 Happy5214 2021-01-31 07:53

The length of [c]freqtable[/c] is [c]num_ideals[/c] (line 430), and [c]ideal[/c] (the index) is greater than that, so the array reference is out-of-bounds and thus we get the segfault. The real question is why there are so many entries in [c]ideal_list[/c] that are above [c]num_ideals[/c].

 henryzz 2021-02-01 16:08

It looks to me that wreck has pointed out some issues that will soon become an issue even if they aren't quite an issue yet. How difficult would it be to future-proof issues 1 and 4? Would changing everything to uint64 increase memory usage a lot in these cases? I am not sure where the bulk of the memory usage is.

 ryanp 2021-02-01 17:41

Thanks for the detailed investigation.

[QUOTE=wreck;570551]5. A question.
Does ryanp give a try to use unique relations less than 1600M?
If done, what's the result?[/QUOTE]

Here's the log from a run with ~1.44B uniques:

[CODE]Fri Jan 1 17:10:48 2021 commencing relation filtering
Fri Jan 1 17:10:48 2021 setting target matrix density to 120.0
Fri Jan 1 17:10:48 2021 estimated available RAM is 192087.4 MB
Fri Jan 1 17:10:48 2021 commencing duplicate removal, pass 1
Fri Jan 1 19:20:20 2021 found 323664961 hash collisions in 1440338304 relation
s
Fri Jan 1 19:20:20 2021 added 1 free relations
Fri Jan 1 19:20:20 2021 commencing duplicate removal, pass 2
Fri Jan 1 19:33:53 2021 found 7 duplicates and 1440338298 unique relations
Fri Jan 1 19:33:53 2021 memory use: 16280.0 MB
Fri Jan 1 19:33:54 2021 reading ideals above 1128464384
Fri Jan 1 19:33:54 2021 commencing singleton removal, initial pass
Fri Jan 1 22:00:14 2021 memory use: 41024.0 MB
Fri Jan 1 22:00:16 2021 reading all ideals from disk
Fri Jan 1 22:00:50 2021 memory use: 28689.1 MB
Fri Jan 1 22:02:12 2021 commencing in-memory singleton removal
Fri Jan 1 22:03:39 2021 begin with 1440338298 relations and 1728567752 unique
ideals
Fri Jan 1 22:08:40 2021 reduce to 54335106 relations and 30002747 ideals in 49
passes
Fri Jan 1 22:08:40 2021 max relations containing the same ideal: 12
Fri Jan 1 22:08:44 2021 reading ideals above 720000
Fri Jan 1 22:08:44 2021 commencing singleton removal, initial pass
Fri Jan 1 22:17:29 2021 memory use: 3012.0 MB
Fri Jan 1 22:17:30 2021 reading all ideals from disk
Fri Jan 1 22:17:33 2021 memory use: 2538.2 MB
Fri Jan 1 22:17:42 2021 keeping 118273914 ideals with weight <= 200, target ex
cess is 278398
Fri Jan 1 22:17:50 2021 commencing in-memory singleton removal
Fri Jan 1 22:17:55 2021 begin with 54335106 relations and 118273914 unique ide
als
Fri Jan 1 22:18:04 2021 reduce to 15293 relations and 0 ideals in 6 passes
Fri Jan 1 22:18:04 2021 max relations containing the same ideal: 0
Fri Jan 1 22:18:04 2021 filtering wants 1000000 more relations
Fri Jan 1 22:18:04 2021 elapsed time 05:07:18[/CODE]

And, for comparison, with 1.85B uniques:

[CODE]Tue Jan 5 11:20:36 2021 commencing relation filtering
Tue Jan 5 11:20:36 2021 setting target matrix density to 120.0
Tue Jan 5 11:20:36 2021 estimated available RAM is 192087.4 MB
Tue Jan 5 11:20:36 2021 commencing duplicate removal, pass 1
Tue Jan 5 15:29:49 2021 found 487341305 hash collisions in 1858202629 relation
s
Tue Jan 5 15:29:49 2021 added 1 free relations
Tue Jan 5 15:29:49 2021 commencing duplicate removal, pass 2
Tue Jan 5 16:45:46 2021 found 9 duplicates and 1858202621 unique relations
Tue Jan 5 16:45:46 2021 memory use: 16280.0 MB
Tue Jan 5 16:45:49 2021 reading ideals above 1440940032
Tue Jan 5 16:45:49 2021 commencing singleton removal, initial pass
Tue Jan 5 22:40:54 2021 memory use: 41024.0 MB
Tue Jan 5 22:40:59 2021 reading all ideals from disk
Tue Jan 5 22:41:53 2021 memory use: 35228.4 MB
Tue Jan 5 22:46:54 2021 commencing in-memory singleton removal
Tue Jan 5 22:51:35 2021 begin with 1858202621 relations and 1929946709 unique
ideals
Tue Jan 5 23:44:19 2021 reduce to 658487197 relations and 538436836 ideals in
28 passes
Tue Jan 5 23:44:19 2021 max relations containing the same ideal: 29
Tue Jan 5 23:45:56 2021 reading ideals above 720000
Tue Jan 5 23:45:58 2021 commencing singleton removal, initial pass
Wed Jan 6 03:03:10 2021 memory use: 21024.0 MB
Wed Jan 6 03:03:13 2021 reading all ideals from disk
Wed Jan 6 03:04:00 2021 memory use: 31064.1 MB
Wed Jan 6 03:08:34 2021 keeping 678560299 ideals with weight <= 200, target ex
cess is 3509174
Wed Jan 6 03:12:51 2021 commencing in-memory singleton removal
Wed Jan 6 03:15:24 2021 begin with 658487197 relations and 678560299 unique id
eals
Wed Jan 6 04:09:33 2021 reduce to 654548247 relations and 674618815 ideals in
22 passes
Wed Jan 6 04:09:33 2021 max relations containing the same ideal: 200
Wed Jan 6 04:11:48 2021 filtering wants 1000000 more relations
Wed Jan 6 04:11:48 2021 elapsed time 16:51:13[/CODE]

In both cases, filtering ran to completion and didn't get stuck. Where I started to run into problems was this run onwards:

[CODE]Wed Jan 6 15:21:43 2021 found 535727162 hash collisions in 1974476487 relation
s
Wed Jan 6 15:21:43 2021 added 1 free relations
Wed Jan 6 15:21:43 2021 commencing duplicate removal, pass 2
Wed Jan 6 16:50:15 2021 found 9 duplicates and 1974476479 unique relations[/CODE]

From roughly 1.9B relations onward, it repeatedly got stuck in "commencing 2-way merge".

 henryzz 2021-02-01 19:15

It looks like reducing the large prime bound to 35 bits might be the best solution. Has this been tried yet?

 ryanp 2021-02-02 00:38

[QUOTE=henryzz;570679]It looks like reducing the large prime bound to 35 bits might be the best solution. Has this been tried yet?[/QUOTE]

I'm running the [C]grep[/C] now, and will try a run - but I think frmky may have already tried this?

 frmky 2021-02-03 06:54

[QUOTE=henryzz;570679]It looks like reducing the large prime bound to 35 bits might be the best solution. Has this been tried yet?[/QUOTE]

Yes. No success. With the start of the semester I've been very busy. Hopefully later this week or next week I'll test out some of wreck's ideas.

 frmky 2021-02-03 07:37

[QUOTE=wreck;570551]
1. From common/filter/filter_priv.h
The definition of ideal_map_t is
typedef struct {
uint32 payload : 30; /* offset in list of ideal_relation_t
structures where the linked list of
ideal_relation_t's for this ideal starts */
uint32 clique : 1; /* nonzero if this ideal can participate in
a clique */
uint32 connected : 1; /* nonzero if this ideal has already been
added to a clique under construction */
} ideal_map_t;
If the ideal is more than 1000M in function purge_cliques_core(),
it is possible that the filter would not work properly.
Here when entering into purge_cliques_core function, the
relation count is 992888838, less than 2^30, so here this 30 bit should not
be the reason of the crash.

4. In function purge_cliques_core(), Line 370
the variable num_reverse is possiblly exceed 2^32,
while its type is uint32.
[/QUOTE]

For 4, if num_reverse exceeds 2^32, then ideal_map[ideal].payload has definitely exceeded 2^30. As a quick and dirty check of the latter, I edited filter_priv.h to

typedef struct {
uint64 payload : 32; /* offset in list of ideal_relation_t
structures where the linked list of
ideal_relation_t's for this ideal starts */
uint64 clique : 1; /* nonzero if this ideal can participate in
a clique */
uint64 connected : 1; /* nonzero if this ideal has already been
added to a clique under construction */
} ideal_map_t;

and started an overnight run. I know this isn't optimal for memory usage, but let's see if it gets us there.

 frmky 2021-02-04 07:02

And that didn't work. Same crash in the same place.

[CODE]commencing duplicate removal, pass 2
found 9 duplicates and 2074342591 unique relations
memory use: 16280.0 MB
commencing singleton removal, initial pass
memory use: 41024.0 MB
memory use: 39309.4 MB
commencing in-memory singleton removal
begin with 2074342591 relations and 1985137022 unique ideals
reduce to 992888838 relations and 765115141 ideals in 20 passes
max relations containing the same ideal: 35
checking relations array at location 5
commencing singleton removal, initial pass
memory use: 21024.0 MB
memory use: 46989.5 MB
keeping 913886427 ideals with weight <= 200, target excess is 5352837
checking relations array at location 1
checking relations array at location 2
commencing in-memory singleton removal
begin with 992888838 relations and 913886427 unique ideals
reduce to 992241034 relations and 913238552 ideals in 15 passes
max relations containing the same ideal: 200
checking relations array at location 5
removing 8630643 relations and 8331224 ideals in 2000000 cliques
checking relations array at location 6
Loc 6: bad relation 983610390 of 983610391, num_ideals is 913238552
rel_index: 15834702, ideal_count: 36, gf2_factors: 69, connected: 156
Ideals: 885450581, 598542783, 158747510, 638930804, 786848709, 2057043263, 3845, 186587920, 18476918, 67526419, 598542783, 872055544, 2057043265, 2046824196, 3942562, 102078889, 58908383, 865042570, 2057043267, 872418055, 9125741, 85351335, 11880544, 43981132, 865042570, 873512089, 893921179, 2057043271, 2567, 93072473, 26460704, 33365801, 865042570, 517341201, 275602560, 862343378,
Found 1 bad relations in array.
commencing in-memory singleton removal

Program received signal SIGSEGV, Segmentation fault.
0x000000000044a176 in filter_purge_singletons_core (obj=0x6de250, filter=0x7fffffffc0f0) at common/filter/singleton.c:445
445 freqtable[ideal]++;
[/CODE]

The line number is a little different since I added a simple routine to check if relation with an ideal with index greater than num_ideals exists. This code is at
[url]https://github.com/gchilders/msieve_nfsathome/tree/msieve-nfsathome[/url]

So at the end of filter_purge_singletons_core(), the relation set appears fine, but something is going awry in purge_cliques_core() since at the end of the delete_relations() the last relation is bad.

Edit: At this point (uint32 *)curr_relation - (uint32 *)relation_array is nearly 2^35, so those relations at the end aren't even be participating in the purge.

 Happy5214 2021-02-04 07:58

Just to be sure, can you put another check near the beginning of purge_cliques_core()? We want to rule out other code called between the singleton purge and the clique purge.

 frmky 2021-02-04 09:03

[QUOTE=Happy5214;570831]Just to be sure, can you put another check near the beginning of purge_cliques_core()? We want to rule out other code called between the singleton purge and the clique purge.[/QUOTE]

I added a check of the relations at the beginning and before each major loop in purge_cliques_core() and restarted a run. I'll report back tomorrow.

 frmky 2021-02-05 05:36

Right before the call to delete_relations(), the relations array looks fine. At the end of delete_relations(), it's broken. I just noticed that in the loop in that function, the calculation of array_word will overflow. I don't think that should cause the issue since it's just used as a comparison to delete_array[], but next I'll make the addresses in delete_array[] 64-bit and remove the check purge_clique_core() so all relations will participate in the purge and fix this overflow.

 frmky 2021-02-06 09:02

So far, so good. Gone past the place of the previous crash, and looping through clique and singleton removal now. Relations array checks are good so far.

 Happy5214 2021-02-06 12:36

That seems promising. Assuming you're working with Ryan's data, if you can successfully filter it, is it possible to send him the msieve output files so he doesn't have to redo the work?

 ryanp 2021-02-06 14:23

If frmky is able to form a matrix, either he or I can run the LA. I'd also be interested to get the msieve patch so I can try the filtering step myself.

 frmky 2021-02-07 17:39

1 Attachment(s)
[CODE]Sat Feb 6 23:19:11 2021 commencing 2-way merge
Sat Feb 6 23:28:47 2021 reduce to 334640603 relation sets and 328431256 unique ideals
Sat Feb 6 23:28:47 2021 commencing full merge
Sun Feb 7 04:51:15 2021 memory use: 38947.4 MB
Sun Feb 7 04:52:10 2021 found 147393213 cycles, need 147295456
Sun Feb 7 04:53:37 2021 weight of 147295456 cycles is about 19148588285 (130.00/cycle)
Sun Feb 7 04:53:37 2021 distribution of cycle lengths:
Sun Feb 7 04:53:37 2021 1 relations: 11327174
Sun Feb 7 04:53:37 2021 2 relations: 10934036
Sun Feb 7 04:53:37 2021 3 relations: 11762737
Sun Feb 7 04:53:37 2021 4 relations: 11269419
Sun Feb 7 04:53:37 2021 5 relations: 10840433
Sun Feb 7 04:53:37 2021 6 relations: 10270300
Sun Feb 7 04:53:37 2021 7 relations: 9536741
Sun Feb 7 04:53:37 2021 8 relations: 8923986
Sun Feb 7 04:53:37 2021 9 relations: 8177647
Sun Feb 7 04:53:37 2021 10+ relations: 54252983
Sun Feb 7 04:53:37 2021 heaviest cycle: 28 relations
Sun Feb 7 04:54:54 2021 commencing cycle optimization
Sun Feb 7 07:05:08 2021 pruned 42215931 relations
Sun Feb 7 07:05:10 2021 memory use: 34774.5 MB
Sun Feb 7 07:05:11 2021 distribution of cycle lengths:
Sun Feb 7 07:05:11 2021 1 relations: 11327174
Sun Feb 7 07:05:11 2021 2 relations: 11209087
Sun Feb 7 07:05:11 2021 3 relations: 12224988
Sun Feb 7 07:05:11 2021 4 relations: 11643676
Sun Feb 7 07:05:11 2021 5 relations: 11239934
Sun Feb 7 07:05:11 2021 6 relations: 10573210
Sun Feb 7 07:05:11 2021 7 relations: 9830741
Sun Feb 7 07:05:11 2021 8 relations: 9126063
Sun Feb 7 07:05:11 2021 9 relations: 8350544
Sun Feb 7 07:05:11 2021 10+ relations: 51770039
Sun Feb 7 07:05:11 2021 heaviest cycle: 28 relations
Sun Feb 7 07:13:57 2021 RelProcTime: 199990
Sun Feb 7 07:13:57 2021 elapsed time 55:33:18[/CODE]
147.3M matrix! That would take my little 8 nodes about 2.5 months to solve!
Patch is attached. Edit: Had to add .txt to the end to get the forum to accept it.

 ryanp 2021-02-07 18:01

[QUOTE=frmky;571096]147.3M matrix! That would take my little 8 nodes about 2.5 months to solve![/QUOTE]

Any chance you'd be able to run it? :smile:

Otherwise, I'll test out the patch and can try sieving some more.

 frmky 2021-02-07 21:52

It's now in the official msieve SVN, so no need for the patch file. Just grab the latest code.

 frmky 2021-02-08 03:15

[CODE]commencing linear algebra
cycles contain 531217644 unique relations
using 8 quadratic characters above 4294917295
building initial matrix
memory use: 68478.7 MB
matrix is 147295267 x 147295456 (74519.1 MB) with weight 19922810683 (135.26/col)
sparse part has weight 18061791563 (122.62/col)
filtering completed in 2 passes
matrix is 147292440 x 147292629 (74518.9 MB) with weight 19922748759 (135.26/col)
sparse part has weight 18061766673 (122.63/col)
matrix starts at (0, 0)
matrix is 147292440 x 147292629 (74518.9 MB) with weight 19922748759 (135.26/col)
sparse part has weight 18061766673 (122.63/col)
saving the first 48 matrix rows for later
matrix includes 64 packed rows
matrix is 147292392 x 147292629 (71275.3 MB) with weight 17993852562 (122.16/col)
sparse part has weight 17211463600 (116.85/col)
using block size 8192 and superblock size 1966080 for processor cache size 20480 kB
memory use: 73902.4 MB
linear algebra at 0.0%, ETA 35242h 7m92629 dimensions (0.0%, ETA 35242h 7m)[/CODE]
I'll see you in 4 years... :lol:

 VBCurtis 2021-02-08 05:57

[QUOTE=frmky;571129][CODE]
linear algebra at 0.0%, ETA 35242h 7m92629 dimensions (0.0%, ETA 35242h 7m)[/CODE]
I'll see you in 4 years... :lol:[/QUOTE]
Holy {censored}!!!!

I mean, wow. 147M dimensions.... But the ETA seems off- shouldn't this take around 4x as long as 73M dimensions? I solved one that size for 2330L in about 3100hr on a single 10-core Ivy Bridge socket, and around 2000hr when run naively (without MPI) on both 10-core sockets.

I'm not volunteering for ~8000 machine-hours, but it seems an 8-socket mini-cluster should be around 10x faster than this!

Thanks for finding and fixing this bug- I'm happy that we're likely to have msieve at our disposal for jobs as big as we can solve matrices for!

 frmky 2021-02-08 06:49

I was being a bit facetious. I've found it scales closer to d^2.5, so say a little under 6 times as long. And that computer isn't particularly fast. A rough estimate is about 2.5 months on the cluster I most use for NFS@Home numbers.

I'll ask around for cluster time to not set NFS@Home back too far. I doubt any of the currently sieved numbers can be done without at least a small cluster with IB or at least 10GbE.

 ryanp 2021-02-08 23:13

[QUOTE=frmky;571140]I was being a bit facetious. I've found it scales closer to d^2.5, so say a little under 6 times as long. And that computer isn't particularly fast. A rough estimate is about 2.5 months on the cluster I most use for NFS@Home numbers.

I'll ask around for cluster time to not set NFS@Home back too far. I doubt any of the currently sieved numbers can be done without at least a small cluster with IB or at least 10GbE.[/QUOTE]

If you're able to run this on your cluster, that would be greatly appreciated; if not, I also understand. Meanwhile I will continue sieving to see if I can form something resembling a reasonable matrix.

 ryanp 2021-02-10 05:36

Verified the fix in the latest SVN update, and I was able to produce a matrix myself. For comparison, here's an ETA on a 64-core workstation:

[CODE]commencing linear algebra
cycles contain 531218272 unique relations
using 8 quadratic characters above 4294917295
building initial matrix
memory use: 68478.7 MB
matrix is 147294934 x 147295123 (74519.4 MB) with weight 19922890703 (135.26/col)
sparse part has weight 18061865192 (122.62/col)
filtering completed in 2 passes
matrix is 147292104 x 147292281 (74519.2 MB) with weight 19922828489 (135.26/col)
sparse part has weight 18061839994 (122.63/col)
matrix starts at (0, 0)
matrix is 147292104 x 147292281 (74519.2 MB) with weight 19922828489 (135.26/col)
sparse part has weight 18061839994 (122.63/col)
saving the first 240 matrix rows for later
matrix includes 256 packed rows
matrix is 147291864 x 147292281 (69444.9 MB) with weight 16505103766 (112.06/col)
sparse part has weight 15847879420 (107.59/col)
using block size 8192 and superblock size 608256 for processor cache size 25344 kB
memory use: 98165.2 MB
linear algebra at 0.0%, ETA 4273h 0m292281 dimensions (0.0%, ETA 4273h 0m)
checkpointing every 40000 dimensions292281 dimensions (0.0%, ETA 4287h45m)
linear algebra completed 81656 of 147292281 dimensions (0.1%, ETA 4336h46m)[/CODE]

Unfortunately I don't think I can tie up this machine for ~half year, but hopefully some more sieving can bring down the matrix size a bit.

 henryzz 2021-02-10 11:00

[QUOTE=ryanp;571253]Verified the fix in the latest SVN update, and I was able to produce a matrix myself. For comparison, here's an ETA on a 64-core workstation:[/QUOTE]
Is this using MPI? On a multi-cpu system that should help.

 ryanp 2021-02-10 21:27

[QUOTE=henryzz;571258]Is this using MPI? On a multi-cpu system that should help.[/QUOTE]

I don't have a lot of experience using MPI. I tried installing mpirun and the necessary developer libs, and recompiled msieve with MPI=1. I'm getting this error when trying to run, though:

[CODE]$mpirun -np 36 ~/math/msieve-mpi/msieve -v -i ./input.ini -l ./input.log -s ./input.dat -nf ./input.fb -nc2 2,18 Invalid MIT-MAGIC-COOKIE-1 keyInvalid MIT-MAGIC-COOKIE-1 key[workstation:3437987] *** Process received signal *** [workstation:3437987] Signal: Segmentation fault (11) [workstation:3437987] Signal code: Invalid permissions (2) [workstation:3437987] Failing at address: 0x558c64230990 [workstation:3437987] [ 0] /lib/x86_64-linux-gnu/libc.so.6(+0x3bd60)[0x7fa355b7bd60][/CODE]  henryzz 2021-02-11 17:43 [QUOTE=ryanp;571281]I don't have a lot of experience using MPI. I tried installing mpirun and the necessary developer libs, and recompiled msieve with MPI=1. I'm getting this error when trying to run, though: [CODE]$ mpirun -np 36 ~/math/msieve-mpi/msieve -v -i ./input.ini -l ./input.log -s ./input.dat -nf ./input.fb -nc2 2,18
[workstation:3437987] Signal: Segmentation fault (11)
[workstation:3437987] Signal code: Invalid permissions (2)
[workstation:3437987] [ 0] /lib/x86_64-linux-gnu/libc.so.6(+0x3bd60)[0x7fa355b7bd60][/CODE][/QUOTE]

I am no expert on MPI running although there supposed to be a speedup. Posts #229 and #230 from [url]https://mersenneforum.org/showthread.php?t=24211&page=13[/url] would be worth reading.

After googling MIT-MAGIC-COOKIE-1 errors seem to be related to x11. Could you try in console mode? unsetting the display variable may be enough "unset DISPLAY"

There have been issues with different versions of mpi/ubuntu. EdH might be able to help sort through that mess. This could be the same issue.

 ryanp 2021-02-13 15:16

I'm back to sieving for this job again. Currently at 2,136,576,912 uniques. My plan for each ~day: gather new relations sieved, then do an msieve filtering run to see how large the resultant matrix is.

 ryanp 2021-02-17 20:37

Currently at:

[CODE]found 0 duplicates and 2472407741 unique relations
memory use: 31280.0 MB
commencing singleton removal, initial pass
memory use: 41024.0 MB
memory use: 41399.9 MB
commencing in-memory singleton removal
begin with 2472407741 relations and 2048964861 unique ideals
reduce to 1444557329 relations and 911198417 ideals in 16 passes
max relations containing the same ideal: 34
commencing singleton removal, initial pass[/CODE]

With ~2.28B uniques, the matrix size was down to 134M, so hopefully we can push it down a bit further still.

 RichD 2021-02-17 23:45

No wonder this has been the number one most wanted for 15 years or so...

 ryanp 2021-02-19 22:06

Currently running the filtering with [B]2.59B[/B] uniques, and target_density=140.

Previous run (2.47B uniques) managed to get the matrix size down to 125M.

 henryzz 2021-02-19 23:33

What's the target? How does the solving time scale?

 ryanp 2021-02-20 14:46

[QUOTE=henryzz;572061]What's the target? How does the solving time scale?[/QUOTE]

Not sure about the target; something in the 90M to 100M range would be nice. I'm also running up against the sheer size of the relations file, which is now about 200GB even gzip'ed.

 ryanp 2021-02-21 18:38

Assuming the current filtering run (2.59B uniques, target_density=140) succeeds, I will probably start LA afterward. The size of the relations file is becoming the issue at this point.

 ryanp 2021-02-22 14:52

[CODE]commencing linear algebra
cycles contain 408993293 unique relations
using 20 quadratic characters above 4294917295
building initial matrix
memory use: 54264.7 MB
matrix is 118001577 x 118001756 (63095.7 MB) with weight 17614526827 (149.27/col)
sparse part has weight 15360150213 (130.17/col)
filtering completed in 2 passes
matrix is 117998763 x 117998931 (63095.5 MB) with weight 17614443699 (149.28/col)
sparse part has weight 15360119182 (130.17/col)
matrix starts at (0, 0)
matrix is 117998763 x 117998931 (63095.5 MB) with weight 17614443699 (149.28/col)
sparse part has weight 15360119182 (130.17/col)
saving the first 240 matrix rows for later
matrix includes 256 packed rows
matrix is 117998523 x 117998931 (58680.1 MB) with weight 14077102445 (119.30/col)
sparse part has weight 13494642461 (114.36/col)
using block size 8192 and superblock size 608256 for processor cache size 25344 kB
memory use: 80685.9 MB
linear algebra at 0.0%, ETA 2503h12m998931 dimensions (0.0%, ETA 2503h12m)
checkpointing every 50000 dimensions998931 dimensions (0.0%, ETA 2521h18m)
linear algebra completed 484175 of 117998931 dimensions (0.4%, ETA 2391h22m)[/CODE]

Doable, but slow; fortunately frmky has offered to lend a hand with the LA in a few weeks' time.

 ryanp 2021-03-05 19:08

After getting up to 2.8B uniques, filtering with target_density=150 produced a 109Mx109M matrix.

[CODE]commencing linear algebra
cycles contain 382966629 unique relations
using 20 quadratic characters above 4294917295
building initial matrix
memory use: 51260.2 MB
matrix is 109443738 x 109443915 (61867.3 MB) with weight 17248536158 (157.60/col)
sparse part has weight 15123709456 (138.19/col)
filtering completed in 2 passes
matrix is 109441975 x 109442140 (61867.2 MB) with weight 17248479767 (157.60/col)
sparse part has weight 15123686159 (138.19/col)
matrix starts at (0, 0)
matrix is 109441975 x 109442140 (61867.2 MB) with weight 17248479767 (157.60/col)
sparse part has weight 15123686159 (138.19/col)
saving the first 240 matrix rows for later
matrix includes 256 packed rows
matrix is 109441735 x 109442140 (57387.5 MB) with weight 13866272003 (126.70/col)
sparse part has weight 13292709138 (121.46/col)
using block size 8192 and superblock size 608256 for processor cache size 25344 kB
memory use: 77410.7 MB
linear algebra at 0.0%, ETA 2362h54m442140 dimensions (0.0%, ETA 2362h54m)
checkpointing every 50000 dimensions442140 dimensions (0.0%, ETA 2353h21m)
linear algebra completed 12252 of 109442140 dimensions (0.0%, ETA 2299h53m) [/CODE]

This would probably be doable for me, but will be faster on frmky's MPI cluster.

 VBCurtis 2021-03-05 19:45

Is there a sense that the filtering bug was squashed, and only the size of the dataset is in the way of filtering jobs this size?

Seems 33/35 is better than 33/36 for this job, to shrink the dataset by 25% (say, 2.1B uniques rather than 2.8B).

I suppose it only matters in principle, since matrix size also stands in the way of trying an even-tougher job.

Bravo for slaying this beast, all the same! Well, almost done..

 frmky 2021-03-07 05:23

I think so... Certainly hope so! Filtering with lots of excess relations is still hard so things could go awry there, but with a reasonable excess the remaining limit is 2^32 total, not unique, relations. With prior duplicate and perhaps singleton removal, this permits large runs.

The size of the dataset isn't much of an issue. The filtering running time is dwarfed by both the sieving and LA running times anyway, and someone completing numbers this size likely has access to a computer with sufficient storage and memory.

[CODE]200G Mar 6 01:55 msieve.dat.gz

commencing singleton removal, initial pass
memory use: 41024.0 MB
memory use: 87634.0 MB
keeping 1372156493 ideals with weight <= 200, target excess is 10188461[/CODE]

 lavalamp 2021-03-09 11:38

1 Attachment(s)
Finally finished my ECM work on the t2200 file!

Composites larger than 2^1018 have had 224 curves @ B1=50e3, B2=13.7e6 (25 digit level).

Composites less than 2^1018 have had 1152 curves @ B1=3e6, B2=14e9 (40 digit level).

The total haul is 815 factors, these have been submitted to factordb, and attached to this post.

 Pascal Ochem 2021-03-25 12:10

Thanks! That is a lot of factors, with an explicit lower bound on the ECM effort for these numbers.

 ThomRuley 2021-03-26 16:59

That's a great idea. What is the current ECM status on the t2200 composites?

 ryanp 2021-03-29 18:31

Here's the latest on the #1 MWRB, with frmky lending a helping hand for the LA:

[CODE]linear algebra completed 20216008 of 109441779 dimensions (18.5%, ETA 854h19m)[/CODE]

 ryanp 2021-05-05 18:32

Thanks in large part to frmky's help with the filtering fix and running LA, the #1 MWRB has fallen.

[url]http://factordb.com/index.php?query=6115909044841454629%5E17-1[/url]

 frmky 2021-05-05 18:49

Here's the log for posterity.

[PASTEBIN]ziQFbDHJ[/PASTEBIN]

 pinhodecarlos 2021-05-05 19:50

Congrats, well done gents!

 Pascal Ochem 2021-05-05 20:19

Ryan, frmky, thank you.
Now I explore the subtrees unlocked by the new factors for lower bounds on many parameters of an OPN.

 charybdis 2021-05-05 21:36

[QUOTE=ryanp;577739]Thanks in large part to frmky's help with the filtering fix and running LA, the #1 MWRB has fallen.

[url]http://factordb.com/index.php?query=6115909044841454629%5E17-1[/url][/QUOTE]

:bow wave:

Glad to see this completed successfully without any further bugs. I presume this means the 4G relation limit is now the limiting factor in the size of jobs that can be run with msieve?

 frmky 2021-05-06 01:28

Yes, I think so. Along with computing resources to complete both the sieving and linear algebra.

 wreck 2021-05-06 11:34

Congratulations, it's a pleasure to see that msieve could work without crash when unique relations' count larger than 2000M.

 henryzz 2021-05-06 18:16

Congratulations for finally getting this problematic number done.

 mathwiz 2021-05-08 15:28

[QUOTE=Pascal Ochem;577754]Ryan, frmky, thank you.
Now I explore the subtrees unlocked by the new factors for lower bounds on many parameters of an OPN.[/QUOTE]

Which file(s) of numbers needed will be regenerated as a result of this exploration?

 Pascal Ochem 2021-05-10 20:26

For the factor P220 of the C301, I have factored 1+P220 by finding a P48.
And now the roadblock has completely disappeared for the bound [$]10^{2200}[/$].
I started the full run for proving the bounds [$]10^{2100}[/$] (to see how the weights drop)
and [$]10^{2200}[/$] (to hopefully get a new bound).
They will finish in a few weeks and we will have the new mwrb files.
The tXXXX files are unaffected.

The other parameters where we encountered the C301 are
- The total number of prime factors [$]\Omega[/$]: I try to extend the bound from 111 factors to 115.
- [$]\Omega-2\omega[/$]: trying to go from 51 to 53 seems difficult.
In both cases, C301 was also the worst roadblock, although way less bad than for the bound [$]10^{2100}[/$]
In both cases, there are still a few mild roadblocks in the unlocked subtrees, not worth considering.
There is no available file of composites here.

And my webpage needs an update: C301 was the example to explain how to circumvent roadblocks.

 Pascal Ochem 2021-05-24 21:35

The run with bound [$]10^{2100}[/$] just finished and we see the impact of the C301.
The old file has 1589 composites.
[url]http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt[/url]
The new file has 1192 composites.
[url]http://www.lirmm.fr/~ochem/opn/mwrb2100.txt[/url]

Don't worry if you are working on a composite that has disappeared.
It will re-appear in mwrb2200 once the run with bound [$]10^{2200}[/$] is over, because of the composite [$]\sigma(11^{330})[/$].

 mathwiz 2021-05-24 22:09

[QUOTE=Pascal Ochem;578993]The run with bound [$]10^{2100}[/$] just finished and we see the impact of the C301.
The old file has 1589 composites.
[url]http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt[/url]
The new file has 1192 composites.
[url]http://www.lirmm.fr/~ochem/opn/mwrb2100.txt[/url]

Don't worry if you are working on a composite that has disappeared.
It will re-appear in mwrb2200 once the run with bound [$]10^{2200}[/$] is over, because of the composite [$]\sigma(11^{330})[/$].[/QUOTE]

Does this tell us anything about whether the [$]10^{2200}[/$] run will succeed, or are the two completely independent?

 wblipp 2021-05-25 05:01

@Pascal

6115909044841454629 16

--------------
@mathwiz
As described in [URL="http://www.lirmm.fr/~ochem/opn/"]Pascal's summary page[/URL], he circumvents roadblocks using a process similar to Kevin Hare's process. This can be applied recursively. In principle, the proof can be extended to any level. In practice, each roadblock causes a large number of additional tree terms, and the limit on the proof is how much time he is willing to commit to generating the proof. Pascal's intuition is that the factoring of the C301 reduced the roadblock complexity sufficiently to allow him to complete the 2200 proof in tolerable time. Unless it turns out he has grossly underestimated the time, he will almost certainly stick to the process long enough to complete the 2200 proof.

 ryanp 2021-05-25 05:21

[QUOTE=wblipp;579019]@Pascal

6115909044841454629 16[/QUOTE]

Seems fixed now at least?

[CODE]$curl -s http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt | wc -l 1589$ curl -s http://www.lirmm.fr/~ochem/opn/mwrb2100.txt | wc -l
1192[/CODE]

 ryanp 2021-05-25 16:40

[QUOTE=Pascal Ochem;578993]The run with bound [$]10^{2100}[/$] just finished and we see the impact of the C301.
The old file has 1589 composites.
[url]http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt[/url]
The new file has 1192 composites.
[url]http://www.lirmm.fr/~ochem/opn/mwrb2100.txt[/url]

Don't worry if you are working on a composite that has disappeared.
It will re-appear in mwrb2200 once the run with bound [$]10^{2200}[/$] is over, because of the composite [$]\sigma(11^{330})[/$].[/QUOTE]

I'm doing some ECM work now. Already found one: [url]http://factordb.com/index.php?id=1100000000012016966[/url] (I assume if I just report to FDB, it'll be picked up by Pascal's scraper as usual)?

 wblipp 2021-05-25 21:12

[QUOTE=ryanp;579021]Seems fixed now at least?[/QUOTE]

I needed to clear my cache. Probably worked correctly all along if not cached.

 ryanp 2021-06-01 13:40

[QUOTE=Pascal Ochem;578993]The run with bound [$]10^{2100}[/$] just finished and we see the impact of the C301.
The old file has 1589 composites.
[url]http://www.lirmm.fr/~ochem/opn/old_mwrb2100.txt[/url]
The new file has 1192 composites.
[url]http://www.lirmm.fr/~ochem/opn/mwrb2100.txt[/url]

Don't worry if you are working on a composite that has disappeared.
It will re-appear in mwrb2200 once the run with bound [$]10^{2200}[/$] is over, because of the composite [$]\sigma(11^{330})[/$].[/QUOTE]

I'm down to 1124 composites remaining in my mwrb2100.

Remaining: [url]https://cs.stanford.edu/~rpropper/mwrb2100.txt[/url]
Factors found: [url]https://cs.stanford.edu/~rpropper/opn.txt[/url]

 Pascal Ochem 2021-07-09 10:49

no OPN is smaller than 10^2200

The run for [$]10^{2200}[/$] is now over. The program gave up on the following branches:

[$]127^{192}[/$] / [$]19^2[/$] [$]3^6[/$] [$]1093^2[/$] [$]398581^{102}[/$] / [$]7^2[/$] / [$]13^1[/$]
[$]127^{192}[/$] / [$]19^2[/$] [$]3^6[/$] [$]1093^2[/$] [$]398581^{108}[/$] / [$]7^2[/$] / [$]13^1 [/$]
[$]61^{232}[/$] / [$]13^2[/$] [$]3^2[/$] / [$]5^{520}[/$] / [$]179^{138}[/$] / [$]1789^1[/$]

The first two situations are due to a standard branching on [$]3^6[/$], so that the considered upper bound on the abundancy is [$]\frac32[/$] instead of [$]\frac{1093}{3^6}[/$].
I fixed it by making an exact branching, after [$]127^{192}[/$] / [$]19^2[/$], on every component [$]3^{2i}[/$], that is, even when [$]2i+1[/$] is composite.

There is no such fix for the third situation: we already have exact branchings on [$]13^2[/$], [$]3^2[/$], [$]1789^1[/$], and the abundancy [$]\sigma_{-1}(p^e)[/$] is really close to [$]\sigma_{-1}(p^\infty)=\frac{p}{p-1}[/$] for [$]61^{232}[/$], [$]5^{520}[/$], [$]179^{138}[/$].

The abundancy in this branch is [$]\frac{61}{60}\frac{183}{13^2}\frac{13}{3^2}\frac54\frac{179}{178}\frac{1790}{1789}=1.99999792324886[/$], which is very close to 2.
If we don't get a miraculous ECM factor and if we want to avoid a huge roadblock circumventing, we can use an old school argument:
One copy of 5 comes from [$]\sigma(1789^1)[/$].
The other 519 copies of 5 must come from things of the form [$]\sigma(p^4)[/$] with [$]p\equiv1\pmod{5}[/$]. Moreover, [$]p\ge963121[/$] so that the abundancy is at most 2.
The case of [$]\sigma(p^{5^k-1})[/$] giving [$]5^k[/$] with [$]k\ge2[/$] is ruled out because it is suboptimal for our argument.
Now [$](963121^4)^{519}[/$] is greater than our bound [$]10^{2200}[/$].

 henryzz 2021-07-09 11:46

It might be a good learning exercise to push each of the forbidden factors as far as possible(assuming that previous primes have been forbidden). Working out the logic to circumvent these roadblocks could be an important learning exercise. I know runtime will limit some of the primes but AFAIK some are still quite quick runs.
The logic gained from these circumventions could potentially be used to shorten the current proof.

Unless I have made a mistake 179^139-1 looks factorable with 179*(179^23)^6-1 at 314 digits which looks within reach of nfs@home(or maybe ryanp) which is currently sieving a couple of SNFS candidates with 326 digits.

 wblipp 2021-07-11 05:27

[QUOTE=Pascal Ochem;582876]
The first two situations are due to a standard branching on [$]3^6[/$], ...

I fixed it by making an exact branching, after [$]127^{192}[/$] / [$]19^2[/$], on every component [$]3^{2i}[/$], that is, even when [$]2i+1[/$] is composite.[/QUOTE]

Could I persuade you to explain the rationale for choosing this fix?

In the paper for [$]10^{1500}[/$] you used exact branches on [$]3^2[/$] and [$]3^4[/$], which required additional standard branches at [$]3^8[/$], [$]3^{14}[/$], and [$]3^{24}[/$]. You could have added an exact branch at [$]3^6[/$] by adding standard branches as [$]3^{20}[/$], [$]3^{34}[/$], and [$]3^{48}[/$]. I have thought of two possible reasons that you didn't do this. First, perhaps this wouldn't have been sufficient and more complex exact branches would have been required - [$]3^8[/$] would be particularly complicated. Second, perhaps you judged this growing list of extra standard branches to be aesthetically ugly, and chose the "every component" as more elegant and simpler to explain.

 Pascal Ochem 2021-07-11 13:17

Henry:
Luckily, the ad-hoc argument is simple (and computer-free) thanks to a Fermat prime raised to large power (5^520) and a special prime that is already specified.
It is good enough for now, we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Maybe more important feasible composites will show up after a closer look at the log files of this run.

William:
Assuming subtle mathematical or aesthetical motives is not a good bet this time.
The exact branch at 3^6 that you describe certainly works, but there is no suitable command option to do it, whereas I only had to replace "-X4 3" by "-Y 3".
The expected computational gain is not worth the effort of adding the "-X6" option and the risk to mess with Michael's code.

 lavalamp 2021-07-11 23:26

[QUOTE=Pascal Ochem;583009]we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.[/QUOTE]Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.

 RichD 2021-07-11 23:55

[QUOTE=lavalamp;583032]Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.[/QUOTE]

I don't know of much ECM work except the above post by [B]ryanp[/B] which did a blanket ECM run of the entire file. Based upon the factors found I am guessing about a t60 or t61.

 ryanp 2021-07-12 03:34

[QUOTE=lavalamp;583032]Has it been attacked much with ECM?

Alas it is just above the size that can be run with GPU-ECM.[/QUOTE]

For that one in particular, I've hit it with 110K curves at B1=85e7. May try B1=29e8 next.

 henryzz 2021-09-09 14:06

[QUOTE=Pascal Ochem;583009]Henry:
Luckily, the ad-hoc argument is simple (and computer-free) thanks to a Fermat prime raised to large power (5^520) and a special prime that is already specified.
It is good enough for now, we don't need to rush the factorization of 179^139-1 that would cost dozens of dollars and grams of CO2.
Maybe more important feasible composites will show up after a closer look at the log files of this run.

William:
Assuming subtle mathematical or aesthetical motives is not a good bet this time.
The exact branch at 3^6 that you describe certainly works, but there is no suitable command option to do it, whereas I only had to replace "-X4 3" by "-Y 3".
The expected computational gain is not worth the effort of adding the "-X6" option and the risk to mess with Michael's code.[/QUOTE]

I have finally had time to think further on this and have a few more questions:

Am I correct in thinking that 5 being a Fermat prime made it easier to determine the optimal way of finding all the needed 5s and similar logic could be applied to other primes although less effectively(maybe [$]963121^{519}[/$] rather than [$](963121^4)^{519}[/$]?) Does the special prime need to always be specified as long as it is accounted for(there may be examples of it providing more than one of the prime).
If we can generalize this technique without it becoming ineffective it could reduce the tree significantly. Surely there must be a useful argument for finding the needed 232 61s. Applying this sort of argument to more than one prime at once could get complicated as a term could provide both needed primes. I will think on this further. It shouldn't be too difficult for a program to find a list of the 232 smallest [$]p^x[/$] such that [$]61 | \sigma(p^x)[/$], however, it would be necessary to also check for [$]61^2 | \sigma(p^x)[/$] for [$]\sigma(p^x)[/$] up to twice the size(and 61^3 etc.) which could be harder. Maybe a suboptimal(we underestimate the size) case could be proven.

You mentioned a -Y option above. The version posted at [url]https://www.arthy.org/opn/[/url] doesn't contain this. Are you working with a later version(if so would you be willing to share?)? Am I correct in thinking that the -X2, -X4 and -Y options are only needed for some of the primes to avoid issues but could be removed for other forbidden factors? Theoretically, the -Y could only be used for 127^192 reducing computation in the other trees where 3 appears especially 3^x.

Are we still only forbidding the factors 127,19,7,11,331,31,97,61,13,398581,1093,3,5,307,17? [url]http://www.lirmm.fr/~ochem/opn/efficiency.txt[/url] suggests this was only sufficient up to 1735

The link to the BCR paper [url]http://wwwmaths.anu.edu.au/~brent/pub/pub116.html[/url] is now broken. [url]https://maths-people.anu.edu.au/~brent/pub/pub116.html[/url] seems to work.

All times are UTC. The time now is 21:14.


text:
# Phd thesis tex file

Phd Thesis Tex File 2016 - presidentialmeadows.org For every phd thesis tex tracked with afixed, monthly doctors, there take new andofficials suspended with for400. NU DISSERTATION TEMPLATE IN MIKTEX Download the Northwestern thesis class file. open and compile the nuthesis-template.tex file you installed to. Phd-thesis-template - A LaTeX / XeLaTeX / LuaLaTeX PhD thesis template for Cambridge University Engineering Department (CUED. My PHD Thesis. My own thesis. It includes different tex files using the \input command which leads to a very tidy and readable structure. %%% File encoding is ISO.

## Phd thesis tex file

Phd Thesis Tex File. Allowed to write custom essays asking yourself How do make sure to meet. Was thorough phd thesis tex file to writing vague opening take. Phd thesis tex file type. One of the main goals of students is to make a good personal statement because it is one of the essential requirements they need to meet. Phd Thesis Tex File 2016 - presidentialmeadows.org For every phd thesis tex tracked with afixed, monthly doctors, there take new andofficials suspended with for400. CTAN tex-archive macros latex contrib psu-thesis. Latex Style File For Phd Thesis - topenglishhelpessay.life Latex Style File For Phd Thesis latex style.

CTAN tex-archive macros latex contrib psu-thesis. Latex Style File For Phd Thesis - topenglishhelpessay.life Latex Style File For Phd Thesis latex style. Phd Thesis Tex File. Allowed to write custom essays asking yourself How do make sure to meet. Was thorough phd thesis tex file to writing vague opening take personal. About the LaTeX thesis templates. The thesis templates have been created to make it easy to prepare your thesis using LaTeX while adhering to the MIT Thesis. Phd-thesis-template - A LaTeX / XeLaTeX / LuaLaTeX PhD thesis template for Cambridge University Engineering Department (CUED.

Doing Purdue University Theses Using LaTeX Mark Senn March 6 , master's theses, PhD dissertations. command in your thesis.tex file. PhD Thesis LaTeX Template Files - CommowickPhD Thesis LaTeX Template Files. Here it is. I finally put on this web site the LaTeX template I used for writing my PhD. Creating a PDF File from a LATEX Thesis. For a Ph.D., run pdfLATEX or LATEX on the le abstitle-phd.tex; for a masters thesis, run. Preparing Your Ph.D. Dissertation Using LaTeX Introduction. The Graduate Division now requires that Ph.D. dissertations be submitted electronically as pdf files.

• Doing Purdue University Theses Using LaTeX Mark Senn March 6 , master's theses, PhD dissertations. command in your thesis.tex file.
• Phd thesis tex file type. One of the main goals of students is to make a good personal statement because it is one of the essential requirements they need to meet.
• PhD Thesis LaTeX Template Files. Here it is. I finally put on this web site the LaTeX template I used for writing my PhD. I have been looking for such a thing for a.

Harvard GSAS PhD Thesis LaTeX Template NOTE: This page has nothing to do with `Harvmac' (outdated Harvard TeX macros), or the `Harvard' bibliography style. My PHD Thesis. My own thesis. It includes different tex files using the \input command which leads to a very tidy and readable structure. %%% File encoding is ISO. LaTeX template for PhD thesis. From OpenWetWare. Jump to: navigation, search. start by looking at the introduction.tex file in the folder /1_introduction;. File for Freedom of Information ; Obtain a Police Record Check ; Purchase Items - Police Auction ; Receive a Copy of a.


text:
# nLab Moyal deformation quantization

Contents

### Context

#### Symplectic geometry

symplectic geometry

higher symplectic geometry

# Contents

## Idea

The Moyal product is a formal deformation quantization of a linear Poisson manifold, hence of a vector space $V$ equipped with a Poisson bivector $\pi \in V \wedge V$, regarded as a constant (translation invariant) bivector field.

Moyal quantization serves as an intermediate step in quantization of more general situations:

Given a symplectic manifold, then Moyal quantization applies in each fiber of the tangent bundle. The resulting fiber bundle of Moyal algebras admits a flat connection (non-uniquely) compatible with the algebra structure. The covariantly constant sections of this Moyal-algebra bundle constitute a formal deformation quantization of the symplectic manifold, see at Fedosov's deformation quantization.

With a little care, the Moyal construction applies also to infinite-dimensional Poisson vector spaces such as appear in local field theory. Here the Moyal quantization yields formal deformation quantization of free field theories to perturbative quantum field theories, the result are the Wick algebras of free field theory (Dito 90, Dütsch-Fredenhagen 01). Combining this this with Fedosov's deformation quantization as above yields interacting perturbative quantum field theories as constructed via causal perturbation theory (Collini 16), see at locally covariant perturbative quantum field theory for more on this.

## Definition

The Moyal star product on smooth functions $C^\infty(V)$ is given on $f,g \in C^\infty(V)$ by

$f \star g \coloneqq prod \circ \exp(\hbar \pi)(f , g) \,,$

where in the exponent we regard $\pi$ as an endomorphism on the tensor product $C^\infty(V) \otimes C^\infty(V)$ by differentiation in each argument, where the exponential denotes the corresponding formal power series of iterated applications of this endomorphism, and where $prod \colon C^\infty(V) \otimes C^\infty(V) \to C^\infty(V)$ is the usual pointwise product of functions.

This means that given a choice of basis $\{x^i\}_i$ of $V$ such that $\pi$ has components $\{\pi^{i j}\}_{i j}$ in this basis, the resulting formal power series in the formal parameter $\hbar$ (“Planck's constant”) starts out as

$(f \star g) = f \cdot g + \hbar \sum_{i,j} \pi^{i j} \frac{\partial f}{\partial x^i}\cdot \frac{\partial g}{\partial x^j} + \frac{1}{2} \hbar^2 \sum_{i,j,k, l} \pi^{k l} \pi^{i j} \frac{\partial^2 f}{\partial x^k\partial x^i}\cdot \frac{\partial^2 g}{\partial x^l \partial x^j} + \cdots$

## Properties

### Integral representation

###### Proposition

(integral representation of star product)

If the functions $f,g$ admit Fourier analysis (are functions with rapidly decreasing partial derivatives), then their star product is equivalently given by the following integral expression:

\begin{aligned} \left(f \star_\omega g\right)(x) &= \frac{(det(\omega)^{2n})}{(2 \pi \hbar)^{2n} } \int e^{ - \tfrac{1}{i \hbar} \omega((x - \tilde y),(x-y))} f(y) g(\tilde y) \, d^{2 n} y \, d^{2 n} \tilde y \end{aligned}

(Baker 58, see at star product this prop).

### Via geometric quantization

The Moyal quantization of a Poisson vector space $(V,\pi)$ arises equivalently as the canonical geometric quantization of symplectic groupoids of the symplectic groupoid which is the Lie integration of the corresponding Poisson Lie algebroid (Weinstein 91, p. 446, Garcia-Bondia & Varilly 94, section V, Hawkins 06).

See at star product this prop. for the proof; and see at geometric quantization of symplectic groupoids – Examples – Moyal quantization for more.

## References

The Moyal product was introduced independently in

• Hilbrand Groenewold, On the Principles of elementary quantum mechanics, Physica,12 (1946) pp. 405-460.

• José Moyal, Quantum mechanics as a statistical theory. Mathematical Proceedings of the Cambridge Philosophical Society 45: 99 (1949)

The integral expression (prop. ) is apparently due to

• George A. Baker, Formulation of Quantum Mechanics Based on the Quasi-Probability Distribution Induced on Phase Space, Jr. Phys. Rev. 109, 2198 – Published 15 March 1958 (doi:10.1103/PhysRev.109.2198)

General accounts include

• D. B. Fairlie, Moyal Brackets, Star Products and the Generalised Wigner Function (arXiv:hep-th/9806198)

• Maciej Blaszak, Ziemowit Domanski, Maciej Blaszak, Ziemowit Domanski (arXiv:1009.0150)

The understanding of the Moyal product as the polarized groupoid convolution algebra of the corresponding symplectic groupoid, hence as an example of geometric quantization of symplectic groupoids had been suggested without proof in

• Alan Weinstein, p. 446 in P. Donato et al. (eds.) Symplectic Geometry and Mathematical Physics, (Birkhäuser, Basel, 1991);

and was proven in detail in

In a broader context this was reconsidered in

The observation that Moyal deformation quantization applied to the Peierls-Poisson bracket yields the Wick algebra quantization of free field theories is due to

• J. Dito, Star-product approach to quantum field theory: The free scalar field. Letters in Mathematical Physics, 20(2):125–134, 1990 (spire)

and was amplified in the broader context of perturbative AQFT in

• Michael Dütsch, Klaus Fredenhagen, Perturbative algebraic field theory, and deformation quantization, in Roberto Longo (ed.), Mathematical Physics in Mathematics and Physics, Quantum and Operator Algebraic Aspects, volume 30 of Fields Institute Communications, pages 151–160. American Mathematical Society, 2001

That moreover the corresponding Fedosov deformation quantization based on this free field theory star product yields the causal perturbation theory quantization of interacting field theories is due to

Last revised on April 18, 2020 at 01:43:38. See the history of this page for a list of all contributions to it.


text:
• Create Account

### #ActualSubtle_Wonders

Posted 14 February 2013 - 11:16 AM

One idea is to not fork a new process just to wait for input from a user. Simply using std::cin.get() should suffice:

void wait() {
cout << "Press return key to continue...";
cin.get();
}

Bonus: this code is completely cross platform, and actually does the same thing on all platforms (in contrast, pause and sleep 1 do not do the same thing).

There are lots of non-performance related improvements. Some of your variable names are very poor, "x" and "y" in particular. Your use of the first element of the "sum" array as two unrelated temporary values is very confusing.

Overall, the intent behind the program is not really shining through the code. It is difficult to assess it's correctness without knowing what is supposed to be happening.

Never thought about that!  Thanks a bunch!  You do have some valid points and I can definately concor with your concerns. Two things learned from such a simple code post.  This is bloodly awesome.     I'm doing this more often. hahaha!

### #1Subtle_Wonders

Posted 14 February 2013 - 11:15 AM

One idea is to not fork a new process just to wait for input from a user. Simply using std::cin.get() should suffice:

void wait() {
cout << "Press return key to continue...";
cin.get();
}

Bonus: this code is completely cross platform, and actually does the same thing on all platforms (in contrast, pause and sleep 1 do not do the same thing).

There are lots of non-performance related improvements. Some of your variable names are very poor, "x" and "y" in particular. Your use of the first element of the "sum" array as two unrelated temporary values is very confusing.

Overall, the intent behind the program is not really shining through the code. It is difficult to assess it's correctness without knowing what is supposed to be happening.

Never thought about that!  Thanks a bunch!  You do have some valid points and I can definately concor with your concerns. Two things learned from such a simply code post.  This is bloodly awesome.     I'm doing this more often. hahaha!

PARTNERS


text:
## Trigonometry 7th Edition

$({\frac{\pi}{6},5}),({{\frac{\pi}{3}},{\frac{5}{2}})},({\frac{2\pi}{3},-5}),({{\pi},{\frac{5}{2}}}),({\frac{7\pi}{6},5})$
given $y=5 \cos(2x-\frac{\pi}{3})$ when $x={\frac{\pi}{6}}$ then $y=5\cos{0}=5$ $x={\frac{\pi}{3}}$ then $y=5\cos{\frac{\pi}{3}}={\frac{5}{2}}$ $x={\frac{2\pi}{3}}$ then $y=5\cos{\pi}=-5$ $x={{\pi}}$ then $y=5\cos{\frac{5\pi}{3}}={\frac{5}{2}}$ $x={\frac{7\pi}{6}}$ then $y=3.\cos{2\pi}=5$ then the final answer is : $({\frac{\pi}{6},5}),({{\frac{\pi}{3}},{\frac{5}{2}})},({\frac{2\pi}{3},-5}),({{\pi},{\frac{5}{2}}}),({\frac{7\pi}{6},5})$


text:
### Home > GB8I > Chapter 6 Unit 7 > Lesson INT1: 6.3.3 > Problem6-106

6-106.

Multiply the polynomials. That is, rewrite each product as a sum.

1. $(2x + 1)(3x − 2)$

Use a generic rectangle or some other method to multiply the polynomial.

$6x^2 − x − 2$

1. $(2x + 1)(3x^2 − 2x − 5)$

Refer to (a) for help.